4727. 摆放棋子
很多人的写法都是当前状态往后更新,然后只有3个维度,但是我看到这个题的时候想的就是这个从前面继承的暴力四维dp,就是细节挺多。
然后这个取模是从队友代码偷学来的。感觉非常好使啊,完美的压行了。
做法:
简单dp,f[i][j][k][l]表示前i个点,已经用了j个黑色的妻子,最后一段黑色的妻子长度为k,此时l = 0;为最后一段长度为l的白色妻子,此时k = 0.
然后就是比较细节的转移:
- j从0开始循环
- 要特判 j - 1是不是>=0,当前转移才能进行下去
- 第一维的空间大小要开200
本地wa了无数发的原因。。最后的统计答案,参数写错了。。
int f[N][N][15][15];
void solve()
{
int n1, n2, k1, k2;
cin >> n1 >> n2 >> k1 >> k2;
f[0][0][0][0] = 1;
for (int i = 1; i <= n1 + n2; i++)
{
for (int j = 0; j <= n1; j++)
{
if (j - 1 >= 0) for (int b = 0; b <= k2; b++) (f[i][j][1][0] += f[i - 1][j - 1][0][b]) %= mod;
if (j - 1 >= 0) for (int h = 2; h <= k1; h++) (f[i][j][h][0] += f[i - 1][j - 1][h - 1][0]) %= mod;
for (int h = 0; h <= k1; h++) (f[i][j][0][1] += f[i - 1][j][h][0]) %= mod;
for (int b = 2; b <= k2; b++) (f[i][j][0][b] += f[i - 1][j][0][b - 1]) %= mod;
}
}
int ans = 0;
for (int h = 1; h <= k1; h++) (ans += f[n1 + n2][n1][h][0]) %= mod;
for (int b = 1; b <= k2; b++) (ans += f[n1 + n2][n1][0][b]) %= mod;
cout << ans;
}