cf1415d xor-gun

Jisoo

Obviously transfer, but will\(O(n^3)\), this is very bad

But you can realize that when you transfer the same tree, it is only that it is only that the maximum is worth it.

And does not affect from ourselves

That records the maximum value

#include<iostream> #include<cstdio>#include<vector>#include<queue>#include<cstring>//#define int long longusing namespace std;int f[2005][2005];int pre[2005];template <class T>T read(T &now){	 now=0;	T f=0;	char c=getchar(); 	while(!isdigit(c)){		f=(c=='-');		c=getchar();	}	while(isdigit(c)){		now=(now<<1)+(now<<3)+c-'0';		c=getchar();	}	if(f) now=-now;	return now;}int x;int y;int n,h,de;int ex[2005][2005];int main(){	read(n);read(h);read(de);	for(int i=1;i<=n;++i){		read(x);		for(int j=1;j<=x;++j){			read(y);			ex[i][y]++;		}	}	for(int i=h;i>=0;--i){		for(int j=1;j<=n;++j){			f[i][j]=f[i+1][j]+ex[j][i];			if(i+de<=h){				f[i][j]=max(f[i][j],pre[i+de]+ex[j][i]); 			}			pre[i]=max(pre[i],f[i][j]);		}	//	cout<<pre[i]<<endl;	}	cout<<pre[0];	return 0;}