现有 nn 个男生 mm 个女生要坐成一排, 需要满足对于任意连续的一段, 不存在男女数量之差大于 kk 的情况, 其中 n, m, kn,m,k 由输入数据给定.
蛮好的一道 DP. 可惜我上午做的时候智商不在线. 当时没有仔细考虑「任意连续的区间」, 这个限制, 导致设出了一个奇怪的状态.
一个自然而然的思路就是从左往右确定方案数, 如果我们纪录目前已经有 ii 个男生, jj 个女生的方案数, 那么转移的话就是看下一个位置坐男生还是坐女生.
但是这个状态不保证满足题目中的限制, 而且由于转移分选男生与选女生, 所以应分别记录已经确定的区间当中, 男生数目减去女生数目的最大值, 以及女生数目减去男生数目的最大值. 又由于 DP 的顺序, 只需要记录后缀最大值即可.
公式爆炸, 具体看代码就好.
代码
- #include
- #include
- #include
- #include
- typedef long long ll;
- const int MAXN = 160;
- const int MAXK = 30;
- const int MOD = 12345678;
- int n, m, k;
- int f[MAXN][MAXN][MAXK][MAXK];
- int () {
- scanf("%d %d %d", &n, &m, &k);
- f[0][0][0][0] = 1;
- for (int i = 0; i <= n; i++) {
- for (int j = 0; j <= m; j++) {
- for (int a = 0; a <= std::min(i, k); a++) {
- for (int b = 0; b <= std::min(j, k); b++) {
- if (i < n && a < k) {
- f[i + 1][j][a + 1][std::max(b - 1, 0)] += f[i][j][a][b];
- f[i + 1][j][a + 1][std::max(b - 1, 0)] %= MOD;
- }
- if (j < m && b < k) {
- f[i][j + 1][std::max(a - 1, 0)][b + 1] += f[i][j][a][b];
- f[i][j + 1][std::max(a - 1, 0)][b + 1] %= MOD;
- }
- }
- }
- }
- }
- int ans = 0;
- for (int a = 0; a <= k; a++) {
- for (int b = 0; b <= k; b++) {
- ans += f[n][m][a][b];
- ans %= MOD;
- }
- }
- printf("%d", ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3235921.html