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;

}

巴特西

D. Caesar's Legions

最新文章

热门文章