题解 CF118D 【Caesar's Legions】

lx_zjk · 2019-12-02 18:43:08 · 题解

题目意思

凯撒大帝喜欢让他的士兵列队。假设他的军队有\text{n}个步兵和\text{m}个骑兵。他认为超过\text{k1}个步兵连续排列或是超过\text{k2}个骑兵连续排列是不优雅的。请找出共有多少种优雅的列队方案数。

状态转移方程

队列里已有n个A军队 m个B军队 i, j表示B A军队人数连续的数量

显然\text{i j}中必有一个数为0

我们可以想出状态转移方程式

Code

const int N = 100 + 5;
const int K = 10 + 5;

int n, m, k1, k2, f[N][N][K][K];

int main () {
    read (n); read (m); read (k1); read (k2);
    f[0][0][0][0] = 1;
    for (int i = 0; i <= n; i ++ ) {
        for (int j = 0; j <= m; j ++ ) {
            for (int k = 1; k <= min (k1, i); k ++ ) Add (f[i][j][1][0], f[i][j - 1][0][k]);
            for (int k = 1; k <= min (k2, j); k ++ ) Add (f[i][j][0][1], f[i - 1][j][k][0]);
            for (int k = 1; k <= min (k1, i); k ++ ) Add (f[i][j][0][k], f[i - 1][j][0][k - 1]);
            for (int k = 1; k <= min (k2, j); k ++ ) Add (f[i][j][k][0], f[i][j - 1][k - 1][0]);
        }
    }
    int ans = 0;
    for (int i = 1; i <= k2; i ++ ) Add (ans, f[n][m][i][0]);
    for (int i = 1; i <= k1; i ++ ) Add (ans, f[n][m][0][i]);
    cout << ans << endl;
    return 0;
}