题目传送门

正解

思路

简单 DP

每次考虑这个位置是通过直接向下跳或者跳 Delta 个位置转移过来的情况。

但是我们会发现，我们需要枚举前 Delta 个位置找到最大值，不过，这个可以在处理每一层的时候顺便搞出来

总复杂度 \(O(NH)\)

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
int n,h;
inline int R(){
	int x=0,f=1;char c='c';
	while(c>'9'||c<'0'){f=f*(c=='-'?-1:1);c=getchar();}
	while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int De,qw,wq;
int shi[2333][5333];
int ans[2333][5333];
int maxax[5333],mami;
int main(){
	n=R();h=R();De=R();
	for(int i=1;i<=n;++i){
		qw=R();
		for(int j=1;j<=qw;++j){
			wq=R();
			shi[i][wq]++;
		}
	} 
	for(int i=h;i>=1;--i){
		for(int j=1;j<=n;++j)
		ans[j][i]=max(ans[j][i+1],maxax[i+De])+shi[j][i];
		for(int j=1;j<=n;++j) maxax[i]=max(maxax[i],ans[j][i]);
	}
	printf("%d\n",maxax[1]);
	return 0;
}