洛谷P1107 [BJWC2008]雷涛的小猫 题解

#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
int n,h,d,g[2005],a[2005][2005],dp[2005][2005];
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()]++;
    }
    for(int i=1; i<=h; i++) {
        for(int j=1; j<=n; j++)
            dp[i][j]=dp[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(dp[i][j],g[i]);
    }
    printf("%d",g[h]);
}