P3448 [POI2006]MIS-Teddies

Alex_Wei · 2021-12-14 10:10:48 · 题解

*P3448 [POI2006]MIS-Teddies

POI 合集。

还算有趣的 DP，感觉难度没有黑牌。

奇奇怪怪的限制 + 很小的数据范围，动态规划没跑了。注意到我们根本不需要知道序列长什么样，只要每种玩具放的个数以及最后两个玩具是什么就可以转移了。因此设六维 DP f_{i,j,k,l,m,n} 表示放了 i,j,k,l 个 A1,A2,B1,B2（分别标号为 0,1,2,3），最后两个玩具分别是 m 和 n 的方案数，转移直接枚举下一个放什么，检查一下是否符合题意即可。

空间复杂度可以通过滚动数组优化。时间复杂度四方，有 64 倍常数。

const int N = 39;
const int mod = 1e6;
void add(int &x, int y) {x += y, x >= mod && (x -= mod);}
int a, b, c, d, ans, f[2][N][N][N][4][4];
bool check(int x, int y, int z) {
    if(x == -1) return 1;
    int a = (x & 1) + (y & 1) + (z & 1), b = (x < 2) + (y < 2) + (z < 2);
    return a && a < 3 && b && b < 3;
}
int main(){
    cin >> a >> b >> c >> d, f[0][0][0][0][0][0] = 1;
    for(int I = 0, i = 0; I <= a; I++, i ^= 1) {
        mem(f[i ^ 1], 0, N);
        for(int j = 0; j <= b; j++)
            for(int k = 0; k <= c; k++)
                for(int l = 0, s = I + j + k; l <= d; l++, s++)
                    for(int x = 0; x < 4; x++)
                        for(int y = 0, v; y < 4; y++)
                            if(v = f[i][j][k][l][x][y]) {
                                int q2 = s <= 1 ? -1 : x, q1 = !s ? -1 : y;
                                if(I < a && check(q2, q1, 0)) add(f[i ^ 1][j][k][l][y][0], v);
                                if(j < b && check(q2, q1, 1)) add(f[i][j + 1][k][l][y][1], v);
                                if(k < c && check(q2, q1, 2)) add(f[i][j][k + 1][l][y][2], v);
                                if(l < d && check(q2, q1, 3)) add(f[i][j][k][l + 1][y][3], v);
                            }
    }
    for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) add(ans, f[a & 1][b][c][d][i][j]);
    cout << ans << endl;
    return 0;
}