洛谷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]);
}