CF 118D（dp计数好题）

题目大概说有n1个步兵和n2骑兵要排成一排，连续步兵数不能超过k1个，连续骑兵数不能超过k2个，问有几种排列方案。

dp[i][j][x][y]表示已经有i个步兵j个骑兵参与排列且末尾有x个连续步兵或y个连续骑兵的方案数.

#include <bits/stdc++.h>
using namespace std;
const int mod = 100000000;
const int maxn = 105;
int dp[maxn][maxn][15][15]; 
int main() {
    int n1, n2, k1, k2;
    cin >> n1 >> n2 >> k1 >> k2;
    dp[0][0][0][0] = 1;
    for (int i = 0; i <= n1; i++) {
        for (int j = 0; j <= n2; j++) {
            for (int x = 0; x <= k1; x++) {
                for (int y = 0; y <= k2; y++) {
                    dp[i + 1][j][x + 1][0] += dp[i][j][x][y];//当前位置放步兵，尾部连续步兵的数量增加 （放了步兵后，尾部连续骑兵的数列变为0）
                    dp[i][j + 1][0][y + 1] += dp[i][j][x][y];//当前位置放骑兵，尾部连续骑兵的数量增加 （放了骑兵后，尾部连续步兵的数量变为0）

                    dp[i + 1][j][x + 1][0] %= mod;
                    dp[i][j + 1][0][y + 1] %= mod;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= k1; i++) {
        ans += dp[n1][n2][i][0]; ans %= mod; //统计尾部步兵连续的数量（这个时候尾部自然就不会出现骑兵）
    }
    for (int i = 1; i <= k2; i++) {
        ans += dp[n1][n2][0][i]; ans %= mod;//统计尾部骑兵连续数量（这个时候尾部自然就不会出现步兵）
    }
    cout << ans << endl;
    return 0;
}