[ZJ][BIT+DP] a596. 祖要段考了!!!!!!!!＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2013-01-21 07:07:42| 人1,099| 回1 | 上一篇 | 下一篇

<-- start of blogbody2 -->

[ZJ][BIT+DP] a596. 祖要段考了!!!!!!!!

推 0 收藏 0 0 站台

容：

快要段考了!!!!!!!!!!!!

平常在上的小小高中生 " 祖 " 感到非常的惶!!!! OAO~~

而了他的情造了多的JIZZZ

他把JIZZ成一碗一碗的，然後把一碗一碗的JIZZZ堆成一一的

而他了一件神奇的事~~

面看起高低相且度大於二，就可以"祖的祝福" 技能XD

他感到欣喜若狂!!!!!!

告祖他可以技能次!!

又因可以太多次了~~只要告她 (方法 mod 12345) 就好了!!

入明：

共有1000料。

始出N ( 0<N<=1500 )。

再有N字，分代表各堆的高度，祖已把他堆成一一的~而你不能把它拆!!!! ( 0<=每高度<=30000 )

出明：

出符合技能件的方法%12345

例入： help

5 1 0 2 3 0

例出：

提示：

背景知： Dynamic Programming

共有下列9：

1 0 2

1 0 3

2 3 0

0 3 0

1 3 0

1 0 3 0

0 2 0

1 0 2 0

1 2 0

出：

祖的 JIZZZZZZZZZZZZZZ (管理：eop112358130)

目我研究了一下，不是很懂目要求什。

後他要求的子列的件是，高低高低高低 ... 或低哥低高低高。
其中度要大於等於三。

先看一很容易懂的 TLE O(N^2)

由於度限制要大於二，那先建立一表分前一次是上升，前一次是下降

/**********************************************************************************/
/* Problem: a596 "祖要段考了!!!!!!!!" from 祖的 JIZZZZZZZZZZZZZZ */
/* Language: CPP (1134 Bytes)                                                    */
/* Result: WA(line:52) judge by this@ZeroJudge                                   */
/* Author: morris1028 at 2013-01-20 10:48:48                                     */
/**********************************************************************************/

#include <stdio.h>

int main() {
    int n, i, j, A[1505];
    int dp[1505][2]; // [0] up, [1] down
    int test = 0;
    while(scanf("%d", &n) == 1) {
        if(test++ > 50) break;
        for(i = 0; i < n; i++) {
            scanf("%d", &A[i]);
            dp[i][0] = dp[i][1] = 0;
        }
        for(i = 0; i < n; i++) {
            for(j = 0; j < i; j++) {
                if(A[i] > A[j])
                    dp[i][0]++;
                if(A[i] < A[j])
                    dp[i][1]++;
            }
        }
        int ans = 0;
        for(i = 0; i < n; i++) {
            ans -= dp[i][0] + dp[i][1];
            for(j = 0; j < i; j++) {
                if(A[i] > A[j])
                    dp[i][0] += dp[j][1];
                if(A[i] < A[j])
                    dp[i][1] += dp[j][0];
                if(dp[i][0] >= 12345)
                    dp[i][0] -= 12345;
                if(dp[i][1] >= 12345)
                    dp[i][1] -= 12345;
            }
            ans += dp[i][0] + dp[i][1];
            ans %= 12345;
        }
        printf("%d\n", ans);
    }
    return 0;
}

拉成 BIT 去完成。

/**********************************************************************************/
/* Problem: a596 "祖要段考了!!!!!!!!" from 祖的 JIZZZZZZZZZZZZZZ */
/* Language: C (1506 Bytes)                                                      */
/* Result: AC(388ms, 568KB) judge by this@ZeroJudge                              */
/* Author: morris1028 at 2013-01-20 11:04:31                                     */
/**********************************************************************************/

#include <stdio.h>
#define lowbit(x) (x&(-x))
void modify(int idx, int N, int k, int C[]) {
    while(idx <= N) {
        C[idx] += k, idx += lowbit(idx);
        if(C[idx] >= 12345)
            C[idx] %= 12345;
    }
}
int query(int idx, int C[]) {
    static int sum;
    sum = 0;
    while(idx > 0) {
        sum += C[idx];
        idx -= lowbit(idx);
    }
    return sum%12345;
}
int main() {
    int n, i, j, A[1505];
    int dp[1505][2];
    while(scanf("%d", &n) == 1) {
        int B1[32768] = {}, B2[32768] = {};
        for(i = 0; i < n; i++) {
            scanf("%d", &A[i]);
            A[i]++;
            dp[i][0] = dp[i][1] = 0;
        }
        for(i = 0; i < n; i++) {
            int a1, a2;
            a1 = query(A[i]-1, B1);
            a2 = query(A[i], B1);
            modify(A[i], 32767, 1, B1);
            dp[i][0] = a1;
            dp[i][1] = i-a2;
        }
        for(i = 0; i < 32768; i++)
            B1[i] = B2[i] = 0;
        int ans = 0;
        for(i = 0; i < n; i++) {
            ans -= dp[i][0] + dp[i][1];
            int a1, a2;
            a1 = query(A[i]-1, B2);
            dp[i][0] += a1;
            a2 = query(32767, B1) - query(A[i], B1);
            dp[i][1] += a2;
            modify(A[i], 32767, dp[i][0], B1);
            modify(A[i], 32767, dp[i][1], B2);
            ans += dp[i][0] + dp[i][1];
            ans %= 12345;
        }
        printf("%d\n", (ans+12345)%12345);
    }
    return 0;
}