0w1

CFR 118 D. Caesar's Legions ( DP )

Problem - D - Codeforces
題意:
給兩種人,各有N1, N2這麼多人,現在排成一對,限制各不能連續出現超過K1, K2於連續一排。求方法數。
解法:
dp[ i ][ j ][ k ] : 已考慮第一種人排完 i 個,第二種人 j 個,現在是第一/二種人結尾的隊的狀態下方法數。
轉移的部分用程式碼表達比較清楚。

const int MOD = ( int ) 1e8;

int N1, N2, K1, K2;

void init(){
    cin >> N1 >> N2 >> K1 >> K2;
}

vvvi dp;

void preprocess(){
    dp = vvvi( N1 + 1, vvi( N2 + 1, vi( 2 ) ) );
    dp[ 0 ][ 0 ][ 0 ] = 1;
    dp[ 0 ][ 0 ][ 1 ] = 1;
    for( int i = 0; i <= N1; ++i )
        for( int j = 0; j <= N2; ++j ){
            for( int k = 1; k <= min( K1, N1 - i ); ++k )
                ( dp[ i + k ][ j ][ 1 ] += dp[ i ][ j ][ 0 ] ) %= MOD;
            for( int k = 1; k <= min( K2, N2 - j ); ++k )
                ( dp[ i ][ j + k ][ 0 ] += dp[ i ][ j ][ 1 ] ) %= MOD;
        }
}

void solve(){
    int ans = dp[ N1 ][ N2 ][ 0 ] + dp[ N1 ][ N2 ][ 1 ];
    cout << ans % MOD << endl;
}