[luogu] CF118D Caesar‘s Legions dp求解方案数

前言

这好难 传送门 :

思路

我们定义思维状态表示 : f [ i ] [ j ] [ k 1 ] [ k 2 ] f[i][j][k1][k2] f[i][j][k1][k2] 表示前 i i i个A军队 和前 j j j个 B B B军队中,有 k 1 k1 k1个连续的A和 K 2 K2 K2个

连续的B的方案数

显然,对于k1,k2 必然是有一个为 0

因此状态转移如下 :

f [ i ] [ j ] [ 1 ] [ 0 ] + = f [ i ] [ j − 1 ] [ 0 ] [ k ] f[i][j][1][0] +=f[i][j-1][0][k] f[i][j][1][0]+=f[i][j−1][0][k] f [ i ] [ j ] [ 0 ] [ 1 ] + = f [ i − 1 ] [ j ] [ k ] [ 0 ] f[i][j][0][1]+=f[i-1][j][k][0] f[i][j][0][1]+=f[i−1][j][k][0] f [ i ] [ j ] [ 0 ] [ k ] + = f [ i − 1 ] [ j ] [ 0 ] [ k − 1 ] f[i][j][0][k]+=f[i-1][j][0][k-1] f[i][j][0][k]+=f[i−1][j][0][k−1] f [ i ] [ j ] [ k ] [ 0 ] + = f [ i ] [ j − 1 ] [ k − 1 ] [ 0 ] f[i][j][k][0]+=f[i][j-1][k-1][0] f[i][j][k][0]+=f[i][j−1][k−1][0]

CODE

const int N  = 110,K = 15;
const int MOD = 1e8;

int f[N][N][K][K];
int n,m,k1,k2;
int mx(int x)
{
	if(x>n>>m>>k1>>k2;
	f[0][0][0][0] = 1;
	
	for(int i=0;i