题解 CF118D 【Caesar's Legions】

ModestCoder_ · 2019-08-27 11:55:58 · 题解

不知为何，这道题目我写的其实并不爽快

显然的dp状态，dp_{i,j,k,l}表示用了i个1，j个2，末尾有连续k个1，l个2

显然k与l中肯定其中一个为0，一个不为0，从这可得到边界

转移我便用了刷表法，对dp_{i,j,k,l}进行讨论

• k!=0,l=0:dp_{i,j,k,l}->dp_{i+1,j,k+1,l},dp_{i,j+1,0,1}
• k=0,l!=0:dp_{i,j,k,l}->dp_{i+1,j,1,0},dp_{i,j+1,k,l+1}

累计答案就是ANS=\sum_{i=0}^{k1}\sum_{j=0}^{k2}dp_{n1,n2,i,j}

Code：

#include <bits/stdc++.h>
#define maxn 110
#define qy 100000000
using namespace std;
int n1, n2, k1, k2, dp[maxn][maxn][20][20];

inline int read(){
    int s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
    for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
    return s * w;
}

void upd(int &x, int y){ if ((x += y) >= qy) x -= qy; }

int main(){
    n1 = read(), n2 = read(), k1 = read(), k2 = read();
    dp[1][0][1][0] = dp[0][1][0][1] = 1;
    for (int i = 0; i <= n1; ++i)
    for (int j = 0; j <= n2; ++j)
    for (int k = 0; k <= min(i, k1); ++k)
    for (int l = 0; l <= min(j, k2); ++l){
        if (!k && !l || k && l) continue;
        int tmp = dp[i][j][k][l];
        if (k) upd(dp[i + 1][j][k + 1][l], tmp), upd(dp[i][j + 1][0][1], tmp); else
        upd(dp[i + 1][j][1][0], tmp), upd(dp[i][j + 1][k][l + 1], tmp);
    }
    int ans = 0;
    for (int i = 0; i <= min(n1, k1); ++i)
        for (int j = 0; j <= min(n2, k2); ++j)
            if (!i && !j || i && j) ; else upd(ans, dp[n1][n2][i][j]);
    printf("%d\n", ans);
    return 0;
}