bzoj 1270: [BeijingWc2008]雷涛的小猫 简单dp+滚动数组

1270: [BeijingWc2008]雷涛的小猫

Time Limit: 50 Sec  Memory Limit: 162 MB
[Submit][Status][Discuss]

Description

 

Input

Output

Sample Input

Sample Output

8

HINT

思路：保存i+z的max值；上一行的dp值；

#include<bits/stdc++.h>

using namespace std;

#define ll __int64

#define mod 100000007

#define esp 0.00000000001

const int N=5e3+,M=1e6+,inf=1e9;

int a[N][N];

int dp[N];

int pre[N];

int maxx[N];

void init()

{

    memset(dp,,sizeof(dp));

    memset(a,,sizeof(a));

    memset(pre,,sizeof(pre));

    memset(maxx,,sizeof(maxx));

}

int main()

{

    int x,y,z,i,t;

    while(~scanf("%d%d%d",&x,&y,&z))

    {

        init();

        for(i=;i<=x;i++)

        {

            scanf("%d",&t);

            for(int j=;j<t;j++)

            {

                int v;

                scanf("%d",&v);

                a[v][i]++;

            }

        }

        for(i=y;i>=;i--)

        {

            for(t=;t<=x;t++)

            {

                dp[t]=max(maxx[i+z],pre[t])+a[i][t];

                pre[t]=dp[t];

                maxx[i]=max(maxx[i],dp[t]);

            }

            for(t=;t<=x;t++)

            {

                printf("%d ",dp[t]);

            }

            cout<<endl<<endl;

        }

        int ans=;

        for(i=;i<=x;i++)

        ans=max(ans,dp[i]);

        printf("%d\n",ans);

    }

    return ;

}

/*

3 10 2

3 1 4 10

6 3 5 9 7 8 9

5 4 5 3 6 9

*/