D. Caesar’s Legions

\(状态很容易设计\)

\(设dp[i][j][u][v]表示放了i个1兵种和j个2兵种\)

\(然后u不会0说明末尾放了连续u个1兵种,v不为0说明末尾放了连续v个2兵种\)

#include <bits/stdc++.h>
using namespace std;
const int mod=1e8;
int dp[109][109][11][11],ans;
int main()
{
    int n1,n2,k1,k2;
    cin>>n1>>n2>>k1>>k2;
    dp[0][0][0][0]=1;
    dp[1][0][1][0]=1;
    dp[0][1][0][1]=1;
    for(int i=0;i<=n1;i++)
    for(int j=0;j<=n2;j++)
    {
        for(int q=2;q<=min(i,k1);q++)
            dp[i][j][q][0]=(dp[i][j][q][0]+dp[i-1][j][q-1][0])%mod;

        for(int q=2;q<=min(j,k2);q++)
            dp[i][j][0][q]=(dp[i][j][0][q]+dp[i][j-1][0][q-1])%mod;

        for(int q=1;q<=min(j,k2);q++)
            dp[i][j][1][0]=(dp[i][j][1][0]+dp[i-1][j][0][q])%mod;

        for(int q=1;q<=min(i,k1);q++)
            dp[i][j][0][1]=(dp[i][j][0][1]+dp[i][j-1][q][0])%mod;
    }
    for(int i=1;i<=k1;i++)   ans+=dp[n1][n2][i][0];
    for(int i=1;i<=k2;i++)   ans+=dp[n1][n2][0][i];
    cout<<ans%mod;
}