1270: [BeijingWc2008]雷涛的小猫
Time Limit: 50 Sec Memory Limit: 162 MB
Submit: 836 Solved: 392
[Submit][Status]
Description
Input
Output
Sample Input
Sample Output
8
HINT
Source
题解:
水水的DP。。。
考虑到n*m很小,所以我们可以从下往上DP,记录一个该行的最大值就可以O(1)转移了。
代码:
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #include<iostream> #include<vector> #include<map> #include<set> #include<queue> #include<string> #define inf 1000000000 #define maxn 2100 #define maxm 500+100 #define eps 1e-10 #define ll long long #define pa pair<int,int> #define for0(i,n) for(int i=0;i<=(n);i++) #define for1(i,n) for(int i=1;i<=(n);i++) #define for2(i,x,y) for(int i=(x);i<=(y);i++) #define for3(i,x,y) for(int i=(x);i>=(y);i--) #define mod 1000000007 using namespace std; inline int read() { int x=,f=;char ch=getchar(); while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();} while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();} return x*f; }
int f[maxn][maxn],n,m,h,mx[maxn]; int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); m=read();n=read();h=read();
for1(i,m)
{
int x=read();
for1(j,x)f[i][read()]++;
}
for1(i,n)
{
for1(j,m)f[j][i]+=max(f[j][i-],mx[max(i-h,)]);
for1(j,m)mx[i]=max(mx[i],f[j][i]);
}
int ans=;
for1(i,m)ans=max(ans,f[i][n]);
printf("%d\n",ans); return ; }