codeforces 118D D. Caesar's Legions(dp)

제목 링크:

codeforces 118D

제목 대의:

n1개 1, n2개 2를 주고 k1과 k2는 연속된 1과 2의 최대 길이를 의미하며 구성할 수 있는 합법적인 다른 열의 수량을 묻는다.

제목 분석:

4

점차적으로 추진할 수 있기 때문에 dp를 이용해서 할 수 있다고 생각했어요

4

먼저 우리는 상태를 정의했다. dp[i][j][k][2]는 1 또는 2로 끝나는 것을 의미하고 마지막에 같은 원소의 수량은 k이고 1의 총수는 j의 현재 서열 길이가 i의 직렬 수량이다

4

먼저 상태를 초기화한다. dp[1][1][1][0]= dp[1][0][1]= 1

4

전이 방정식은 다음과 같다.
dp[i][j][1][0]=∑k=1min(k2,i−j)dp[i−1][j−1][k][1]
dp[i][j][1][1]=∑k=1min(k1,j)dp[i−1][j][k][0]
dp[i][j][k][0]=∑k=1min(k1,j)dp[i−1][j−1][k−1][0]
dp[i][j][k][1]=∑k=1min(k2,i−j)dp[i−1][j][k−1][1]

4

최종 결과의 통계 방법:
ans=∑i=1k1dp[n][n1][i][0]+∑i=1k2dp[n][n1][i][1]

AC 코드:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define MAX 107

using namespace std;

int n1,n2,k1,k2;
const int mod = 1e8;
int dp[MAX<<1][MAX][12][2];


int main ( )
{
    while ( ~scanf ( "%d%d%d%d" , &n1 , &n2 , &k1 , &k2 ) )
    {
        memset ( dp , 0 , sizeof ( dp ) );
        dp[1][1][1][0] = 1;
        dp[1][0][1][1] = 1;
        int n = n1+n2;
        for ( int i = 2 ; i <= n; i ++ )
            for ( int j = 0; j <= i && j <= n1 ; j++ )
            {
                for ( int k = 1; k <= k2 && k <= i-j ; k++ )
                {
                    dp[i][j][1][0] += dp[i-1][j-1][k][1];
                    dp[i][j][1][0] %= mod;
                }
                for ( int k = 1; k <= k1 && k <= j ; k++ )
                    if ( i-1 >= j )
                    {
                        dp[i][j][1][1] += dp[i-1][j][k][0];
                        dp[i][j][1][1] %= mod;
                    }
                for ( int k = 2; k <= j&& k <= k1 ; k++ )
                {
                    dp[i][j][k][0] += dp[i-1][j-1][k-1][0];
                    dp[i][j][k][0] %= mod;
                }
                if ( i-1 < j ) continue;
                for ( int k =2 ; k <= i-j && k <= k2 ; k++ )
                {
                    dp[i][j][k][1] += dp[i-1][j][k-1][1];
                    dp[i][j][k][1] %= mod;
                }
            }
        /*cout << "-------------------" << endl; cout << "====================" << endl; cout << dp[3][1][1][0] << endl; cout << "====================" << endl; cout << dp[5][2][1][0] << endl; cout << dp[5][2][1][1] << endl; cout << dp[5][2][2][1] << endl; cout << "-------------------" << endl;*/
        int ans = 0;
        for ( int i = 1 ; i <= k1 ; i++ )
        {
            ans += dp[n][n1][i][0];
            ans %= mod;
        }
        for ( int i = 1 ; i <= k2 ; i++ )
        {
            ans += dp[n][n1][i][1];
            ans %= mod;
        }
        printf ( "%d
" , ans );
    }
}