[BZOJ 1270][BeijingWc2008]雷濤的小貓

[BZOJ 1270][BeijingWc2008]雷濤的小貓

看到題面上的PKU宿捨，又讓我懷念起七月份在PKU上課的那段快樂時光。。。

這也許是WC的送分題吧，比較簡單的動規，但是也很巧妙。用f1[i]表示小貓在高度i時得到的柿子個數最大值，f2[i]表示在當前高度上，小貓在第i根柱子上得到的柿子個數最大值。

然後高度從高到低遍歷，維護f1、f2即可。

#include 
#include 
#include 
#include 
#include 

#define MAXN 5050

using namespace std;

int map[MAXN][MAXN];
int f1[MAXN],f2[MAXN]; //f1[i]=高度為i，貓得到的柿子個數最大值，f2[i]=當前高度貓在第i個柱子上得到的柿子個數最大值

int main()
{
    int n,h,d,ni,t;
    scanf(%d%d%d,&n,&h,&d);
    for(int i=1;i<=n;i++)
    {
        scanf(%d,&ni);
        for(int j=1;j<=ni;j++)
        {
            scanf(%d,&t);
            map[i][t]++;
        }
    }
    for(int i=h;i>=1;i--)
    {
        t=i+d;
        if(t<=h) t=f1[i+d]; //如果貓之前跳躍過，那麼貓在之前的高度上得到的柿子個數最大值為t
        else t=0;
        for(int j=1;j<=n;j++)
        {
            f2[j]=max(f2[j],t)+map[j][i];
            f1[i]=max(f1[i],f2[j]);
        }
    }
    printf(%d
,f1[1]);
    return 0;
}