Morris' Blog

2013-01-21 07:07:42Morris

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

留言 1 收藏 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;
}

上一篇：[ZJ][DFS/BFS] a597. 祖靈被榨乾了!!!!!!!!

下一篇：[ZJ][DFS剪枝] b153. NOIP2004 4.虫食算