CFR 543 A. Writing Code ( DP )

Problem - 543A - Codeforces
題意：
給 N, M, B, MOD, 分別是編程者數量，程式碼行數，可容忍的 bug最大上限數，和神秘餘數。接著一行給出各編程者一行會寫出多少 bug。從一號開始，每個編程者完成剩餘的行數中任意多個( 0 ~ 完成 )，求完成指定的程式碼行數前提下，bug的數量不超過指定上限的方案數對 MOD餘數。
解法：
dp[ i ][ j ][ k ] : 考慮前 i 個編程者，已完成 j 行，目前有 k 個 bug 的方案數。
dp[ i ][ j ][ k ] = SIGMA{ dp[ i - 1 ][ j ][ k ] } + SIGMA{ dp[ i ][ j - 1 ][ k - A[ i - 1 ] ] }
由於記憶體花費較大，這裡使用滾動陣列進行動態規劃。

int N, M, B, MOD;
vi A;

void init(){
    cin >> N >> M >> B >> MOD;
    A = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];
}

vvvi dp;

void preprocess(){
    dp = vvvi( 2, vvi( M + 1, vi( B + 1 ) ) );
    dp[ 0 ][ 0 ][ 0 ] = 1;
    for( int i = 1; i <= N; ++i ){
        int t = i & 1;
        for( int j = 0; j <= M; ++j )
            for( int k = 0; k <= B; ++k ){
                dp[ t ][ j ][ k ] = dp[ t ^ 1 ][ j ][ k ];
                if( j - 1 >= 0 and k - A[ i - 1 ] >= 0 )
                    ( dp[ t ][ j ][ k ] += dp[ t ][ j - 1 ][ k - A[ i - 1 ] ] ) %= MOD;
            }
    }
}

void solve(){
    int ans = 0;
    for( int i = 0; i <= B; ++i )
        ( ans += dp[ N & 1 ][ M ][ i ] ) %= MOD;
    cout << ans << endl;
}