Problem Specification Value
Time Limit 10 Sec
Memory Limit 162 MB
Submit 1967
Solved 1165

Description

今天是 hidadz 小朋友的生日, 她邀请了许多朋友来参加她的生日 party. hidadz 带着朋友们来到花园中, 打算坐成一排玩游戏. 为了游戏不至于无聊, 就座的方案应满足如下条件: 对于任意连续的一段, 男孩与女孩的数目之差不超过 k. 很快, 小朋友便找到了一种方案坐了下来开始游戏. hidadz 的好朋友 Susie 发现, 这样的就座方案其实是很多的, 所以大家很快就找到了一种, 那么到底有多少种呢? 热爱数学的 hidadz 和她的朋友们开始思考这个问题...... 假设参加 party 的人中共有 n 个男孩与 m 个女孩, 你是否能解答 Susie 和 hidadz 的疑问呢? 由于这个数目可能很多, 他们只想知道这个数目除以 12345678 的余数.

Input

仅包含一行共 3 个整数, 分别为男孩数目 n, 女孩数目 m, 常数 k.

Output

应包含一行, 为题中要求的答案.

Sample Input

1 2 1

Sample Output

1

HINT

n, m ≤ 150, k ≤ 20.

Source

http: //www. cnphp6. com/archives/61515 看来自己越来越弱了......

这些计数题设计的状态都很巧妙,, 自己智商太低 QAQ

和矩阵 dp 做的那题差不多, 都是枚举当前点的情况然后开了一些维来维护从当前点向前延伸的一些状态.

设 d [i, j, x, y] 表示前 i 个男的前 j 个女的, x 表示从当前点向前延伸得到的最大的男减女的差, y 表示从当前点向前延伸得到的最大的女减男的差.

则 d [i+1, j, x+1, max (y-1, 0)] +=d [i, j, x, y], d [i, j+1, x, max (y-1, 0)] +=d [i, j, x, y]

这样设计状态能不重不漏的统计且能转移是因为, 转移的点是 i+1, j+1, 而 x 和 y 设计的状态只用考虑当前的和 i+1 或 j+1 这个点

还有个地方我竟然考虑了很久? 就是 max 那里, 会不会不正确? 但是想想就应该知道, 假如变成了-1, 那么总有办法从前边去掉一个使得变成 0, 而我们所设计的状态要保证任意一段最大, 所以存在了最大的段, 即 0

最后答案就是 sum {d [n, m, x, y], 0<=x, y<=k}

连这么水的 DP 都想不出来真是没脸见人了~


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
const int mod = 12345678;

int n, m, k;
int dp[160][160][25][25];

int main(int argc, char** argv)
{
    scanf("%d%d%d", &n, &m, &k);
    dp[0][0][0][0] = 1;
    for (int i = 0; i <= n; i++) // Counting i boys
        for (int j = 0; j <= m; j++) // Counting j girls
            for (int x = 0; x <= k; x++) // There are x more boys than girls up to now
                for (int y = 0; y <= k; y++) { // There are y more girls than boys up to now
                    // This time it's completely empty, and shall not care about it...
                    if (dp[i][j][x][y] <= 0) continue;
                    if (i < n && x < k) // Adding a boy
                        dp[i + 1][j][x + 1][max(y - 1, 0)] =
                                (dp[i + 1][j][x + 1][max(y - 1, 0)] +
                                dp[i][j][x][y]) % mod;
                    if (j < m && y < k) // Adding a girl
                        dp[i][j + 1][max(x - 1, 0)][y + 1] =
                                (dp[i][j + 1][max(x - 1, 0)][y + 1] +
                                dp[i][j][x][y]) % mod;
                }
    // Of course, the sum is all of the states of the last timestamp, i.e.
    // for each 0 <= x, y <= k, we give dp[n][m][x][y] to the sum
    int sum = 0;
    for (int x = 0; x <= k; x++)
        for (int y = 0; y <= k; y++)
            sum = (sum + dp[n][m][x][y]) % mod;
    printf("%d\n", sum);
    return 0;
}
from pydatagen import *
x = randrange(90, 150)
y = x + randrange(-150 + x, 150 - x)
k = randrange(2, 20)
printf('%d %d %d\n' % (x, y, k))
fclose()