P1107 雷涛的小猫

　　这道题这么简单，本来都不想写……但是出于对小猫无限的热爱，还是来发一篇题解。>\<

　　标签是贪心，但是我用dp做。一开始是想对于每一个高度，枚举树编号，找出最优情况，但复杂度O(n³)，

显然过不了。那一瞬间我还怀疑到底能不能用dp做……

　　但是解决方法肯定是有的，对于一个高度能带来的最大值，可以开一个数组记下来，下一次就不用暴力去算了（快夸我聪明），但是也要注意更新。

　　AC后看了一下题解，发现有的题解用的竟然就是我的方法，顿时很有成就感啊~~~

　　代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#define maxn 2005
using namespace std;
int dp[maxn][maxn],tree[maxn][maxn],n,h,d,s[maxn];
int main()
{
    scanf("%d%d%d",&n,&h,&d);
    for(int i=1; i<=n; i++)
    {
        int num;
        scanf("%d",&num);
        for(int j=1; j<=num; j++)
        {
            int x;
            scanf("%d",&x);
            tree[i][x]++;
        }
    }
    for(int i=1; i<=n; i++)
    {
        dp[i][1]=tree[i][1];
        s[1]=max(s[1],dp[i][1]);
    }
    for(int j=2; j<=h; j++)
    {
        for(int i=1; i<=n; i++)
            dp[i][j]=dp[i][j-1]+tree[i][j];
        if(j>=d)
            for(int i=1; i<=n; i++)
                dp[i][j]=max(dp[i][j],s[j-d]+tree[i][j]);
        for(int i=1; i<=n; i++)
            s[j]=max(s[j],dp[i][j]);
    }
    printf("%d",s[h]);
    return 0;
}