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; }