f ( i , j , k , u ) f(i, j, k, u) f(i,j,k,u) —— 表示选 i i i 个黑子， j j j 个白子，末尾有连续 k k k 个棋子， u = 0 u = 0 u=0 表示末位是黑子， u = 1 u = 1 u=1 表示末位是白子。
状态转移方程：若末位只有一个连续棋子需要特判
f ( i , j , k , 0 ) = f ( i − 1 , j , k − 1 , 0 ) f(i, j, k, 0) = f(i - 1, j, k - 1, 0) f(i,j,k,0)=f(i−1,j,k−1,0)
f ( i , j , k , 1 ) = f ( i , j − 1 , k − 1 , 1 ) f(i, j, k, 1) = f(i, j - 1, k - 1, 1) f(i,j,k,1)=f(i,j−1,k−1,1)
f ( i , j , 1 , 0 ) + = f ( i − 1 , j , k , 1 ) f(i, j, 1, 0) += f(i - 1, j, k, 1) f(i,j,1,0)+=f(i−1,j,k,1)
f ( i , j , 1 , 1 ) + = f ( i , j − 1 , k , 0 ) f(i, j, 1, 1) += f(i, j - 1, k, 0) f(i,j,1,1)+=f(i,j−1,k,0)
时间复杂度 O ( n 1 n 2 × ( k 1 + k 2 ) ) O(n_1 n_2 \times (k_1 + k_2)) O(n1n2×(k1+k2))
#include#include
#include#define endl '\n'
#define fup(i, a, b) for (int i = a; i<= b; i ++ )
#define fdn(i, a, b) for (int i = a; i >= b; i -- )
using namespace std;
typedef long long LL;
const int N = 110, M = 15, MOD = 1e8;
int n, m, x, y;
int f[N][N][M][2];
void add(int &a, int b)
{a = (a + b) % MOD;
}
int main()
{cin >>n >>m >>x >>y;
f[1][0][1][0] = f[0][1][1][1] = 1;
fup(i, 0, n) fup(j, 0, m)
{if (i)
{fup(k, 2, x) f[i][j][k][0] = f[i - 1][j][k - 1][0];
fup(k, 1, y) add(f[i][j][1][0], f[i - 1][j][k][1]);
}
if (j)
{fup(k, 2, y) f[i][j][k][1] = f[i][j - 1][k - 1][1];
fup(k, 1, x) add(f[i][j][1][1], f[i][j - 1][k][0]);
}
}
int res = 0;
fup(i, 1, x) add(res, f[n][m][i][0]);
fup(i, 1, y) add(res, f[n][m][i][1]);
cout<< res<< endl;
return 0;
} f ( i , j , k ) f(i, j, k) f(i,j,k) 表示摆好前 i i i 个棋子，其中有 j j j 个白棋， k = 0 k = 0 k=0 表示最后一位为黑棋， k = 1 k = 1 k=1 表示最后一位为白棋。
状态转移方程：若最后一位是白棋，则枚举砍掉最后多少位后剩下的序列的最后一位是黑棋，这里枚举砍掉 k k k 位的范围是 1 ⩽ k ⩽ m i n ( j , x ) 1 \leqslant k \leqslant min(j, x) 1⩽k⩽min(j,x)，表示最后砍掉的部分不能超过当前枚举的连续段的上限以及题目所给的连续长度的上限，下面同理；若最后一位是黑棋，则枚举砍掉最后多少位后剩下的序列的最后一位是白棋，这里枚举砍掉 k k k 位的范围是 1 ⩽ k ⩽ m i n ( i − j , y ) 1 \leqslant k \leqslant min(i - j, y) 1⩽k⩽min(i−j,y)。
f ( i , j , 1 ) + = f ( i − k , j − k , 0 ) f(i, j, 1) += f(i - k, j - k, 0) f(i,j,1)+=f(i−k,j−k,0)
f ( i , j , 0 ) + = f ( i − k , j , 1 ) f(i, j, 0) += f(i - k, j, 1) f(i,j,0)+=f(i−k,j,1)
时间复杂度 O ( ( n 1 + n 2 ) × k 2 ) O((n_1 + n_2) \times k_2) O((n1+n2)×k2)#include#include
#include#define endl '\n'
#define fup(i, a, b) for (int i = a; i<= b; i ++ )
#define fdn(i, a, b) for (int i = a; i >= b; i -- )
using namespace std;
const int N = 110, M = N<< 1, S = 15, MOD = 1e8;
int n, m, x, y;
int f[M][N][S];
int add(int &a, int b)
{return a = (a + b) % MOD;
}
int main()
{cin >>n >>m >>x >>y;
n += m;
f[0][0][0] = f[0][0][1] = 1;
fup(i, 1, n) fup(j, 0, min(i, m))
{fup(k, 1, min(j, y)) add(f[i][j][1], f[i - k][j - k][0]);
fup(k, 1, min(i - j, x)) add(f[i][j][0], f[i - k][j][1]);
}
cout<< add(f[n][m][0], f[n][m][1])<< endl;
return 0;
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
