CF478D Red-Green Towers 题解 动态规划

题目链接：https://codeforces.com/problemset/problem/478/D

解题思路：

定义 (f[i][j]) 表示第 (i) 层并且总使用了 (j) 个红色格子的方案总数。

则：(f[i][j] = f[i-1][j] + f[i-1][j-h])（要注意状态 (f[i-1][j]) 和 (f[i-1][j-h]) 的合法性）。

因为空间达到了 (O(n^{frac{3}{2}})) 所以考虑第一维使用滚动数组压缩。

然后遍历状态的时候用一个 (vis) 数组判断一下是不是最后一层（如果这一层扩展不出来任何新的状态，那么这一层的上一层就是最后一层）。

示例代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200020;
const long long MOD = 1000000007LL;
int r, g;
long long f[2][maxn];
bool ok[2][maxn];
int main() {
    cin >> r >> g;
    f[0][0] = 1;
    ok[0][0] = true;
    long long sum = 0;
    for (int h = 1; ; h ++) {
        bool flag = false;
        int tot = h * (h+1) / 2;
        int i = h & 1;
        long long tmp = 0;
        for (int j = max(0, tot-g); j <= min(tot, r); j ++) {
            f[i][j] = 0;
            ok[i][j] = false;
            if (ok[i^1][j]) {
                ok[i][j] = flag = true;
                f[i][j] = (f[i][j] + f[i^1][j]) % MOD;
            }
            if (j-h >= 0 && ok[i^1][j-h]) {
                ok[i][j] = flag = true;
                f[i][j] = (f[i][j] + f[i^1][j-h]) % MOD;
            }
            tmp = (tmp + f[i][j]) % MOD;
        }
        if (!flag) {
            cout << sum << endl;
            break;
        }
        sum = tmp;
    }
    return 0;
}