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

题目链接：

codeforces 118D

题目大意：

给出n1个1，n2个2，给出k1和k2代表连续的1和2的最大长度，问能够构造的合法的不同串的数量。

题目分析：

• 能够递推，所以想到能够利用dp做。
• 首先我们定义状态，dp[i][j][k][2]代表以1或2结尾，结尾相同的元素的数量为k，1的总数是j的当前序列长度为i的串的数量。
• 首先是对状态进行初始化，dp[1][1][1][0] = dp[1][0][1][1] = 1
• 转移方程如下：
  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]
• 最终结果的统计方法：
  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\n" , ans );
    }
}