cf1415d xor-gun


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;}