首页 > 代码库 > BZOJ 1270 雷涛的小猫

BZOJ 1270 雷涛的小猫

普及组dp。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 2050using namespace std;int n,h,del,x,y,tab[maxn][maxn],mx[maxn*3],f[maxn][maxn],ans=0;int main(){    scanf("%d%d%d",&n,&h,&del);    for (int i=1;i<=n;i++)    {        scanf("%d",&x);        for (int j=1;j<=x;j++)        {            scanf("%d",&y);            tab[i][y]++;        }        }    for (int i=h;i>=1;i--)    {        for (int j=1;j<=n;j++)            f[j][i]=max(mx[i+del],f[j][i+1])+tab[j][i];        for (int j=1;j<=n;j++)            mx[i]=max(mx[i],f[j][i]);    }    for (int i=1;i<=n;i++)        ans=max(ans,f[i][1]);    printf("%d\n",ans);    return 0;        }

 

BZOJ 1270 雷涛的小猫