弱弱的dp我也会做！哈哈哈

设f[i][j]表示高度为i时，在第j个树上能吃到的果子数的最大值。m[i]表示高度为i时吃到的果子数的最大值。w[i][j]表示高度为i，第j颗树上的果子树。

那么方程显而易见：f[i][j]=max(f[i+1][j],m[i+d])+w[i][j]。

读入文件好像奇大、好可怕、话说一开始MLE了、、囧不得不开short、、

orz读入优化、瞬间提升5s、

#include<cstdio>
#define max(a,b) (((a)<(b))?(b):(a))
int n,h,d,k,t,i,j,f[5005][5005]={0},m[5005]={0};    short a[5005][5005]={0};
inline void read(int &x){
    char ch;    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    x=ch-'0';   for(ch=getchar();ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
}int main(){
    for(read(n),read(h),read(d),i=1;i<=n;i++)for(read(t),j=1;j<=t;j++)read(k),a[i][k]++;
    for(i=h;~i;i--){
        if(i+d<=h)  t=m[i+d];   else    t=0;
        for(j=1;j<=n;j++)   f[i][j]=max(f[i+1][j],t)+a[j][i],   m[i]=max(m[i],f[i][j]);
    }printf("%d",m[0]); return 0;
}

• 相关文章