题目描述

 

输入

输出

样例输入

样例输出

8

---

题解

dp

设f[i][j]表示在第i棵树的j高度时最多吃到的柿子数。

那么只有两种可能能够到达这个位置：滑下来、跳下来。

滑下来直接用f[i][j+1]转移，跳下来需要在dp同时记录一个g数组，g[j]表示j高度时最多的柿子数，这样可以用g[j+D]转移。

然后跑dp即可。

#include 
     
      #include 
      
       #define N 2010using namespace std;int f[N][N] , num[N][N] , g[N];inline int read(){	int ret = 0; char ch = getchar();	while(ch < '0' || ch > '9') ch = getchar();	while(ch >= '0' && ch <= '9') ret = (ret << 3) + (ret << 1) + ch - '0' , ch = getchar();	return ret;}int main(){	int n , m , d , k , i , j;	n = read() , m = read() , d = read();	for(i = 1 ; i <= n ; i ++ )	{		k = read();		while(k -- ) num[i][read()] ++ ;	}	for(j = m ; ~j ; j -- )	{		for(i = 1 ; i <= n ; i ++ )		{			f[i][j] = f[i][j + 1] + num[i][j];			if(j + d <= m) f[i][j] = max(f[i][j] , g[j + d] + num[i][j]);			g[j] = max(g[j] , f[i][j]);		}	}	printf("%d\n" , g[0]);	return 0;}