洛谷P1107 - 雷涛的小猫

我们根据题意，发现这是一个 DP 题，定义 $f_{i,j}$ 表示在高度为 $i$，当前要爬的树为 $j$ 所能获得的最大柿子数。

易得状态转移方程：$f_{i,j}=max(f_{i-1,j},f_{i-delta,k}) (1\leq k \leq n)$，当 $i>delta$ 时后一项成立。

于是我们得到了一个时间复杂度为 $O(H \times N^2)$，空间复杂度为 $O(N \times H)$ 的算法啦。。

然而 $N,H=2000$ 的数据这个时间复杂度还是难以承受，所以需要进一步的优化。

我们发现对于每个 $i$，第二个转移的 $i-delta$ 总是固定的，所以就可以直接处理出高度为 $i$ 时 $f_{i,j}$ 的最大值，时间复杂度降到 $O(N \times H)$

接下来上代码：

#include <cstdio>
#include <iostream>
using namespace std;
#define gc ch = getchar()
inline int read() {
    int x = 0,f = 1; char gc;
    for (; ch < '0' || ch > '9'; gc) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; gc) x = x * 10 + ch - '0';
    return x * f;
}
#undef gc
// 以上为快读，听说不用读入优化会TLE,比如cin、cout
int n, h, d, g[2005], a[2005][2005], f[2005][2005];
// g[i]表示高度为i时f[i][j]的最大值
int main() {
    n = read(); h = read(); d = read();
    for (int i = 1; i <= n; i++) {
        a[i][0] = read();
        for(int j = 1; j <= a[i][0]; j++) a[i][read()]++;
        // 注意，是每个上面有1个，所以要加一，而不是赋值为一
    }
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= n; j++) f[i][j] = f[i - 1][j] + a[j][i];
        if (i > d) for (int j = 1; j <= n; j++) f[i][j] = max(f[i][j], g[i - d] + a[j][i]);
        for (int j = 1; j <= n; j++) g[i] = max(f[i][j], g[i]);
        // 转移见上
    }
    printf("%d", g[h]);
}