【BZOJ】1270: [BeijingWc2008]雷涛的小猫（DP+水题）

http://www.lydsy.com/JudgeOnline/problem.php?id=1270

这完全是一眼题啊，但是n^2的时间挺感人。（n^2一下的级别请大神们赐教，我还没学多少dp优化。。）

一眼是n^3的，但是马上可以想到n^2的，用一个数组维护每层最大就行了。

在这里，dp的数组开n^2和存图的数组开n^2用int的话一定爆，存图的用short可以水过。但是看方程我们可以很自然的想到用滚动数组，那么dp的数组就变成一维的啦～ac无压力。

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define for1(i,a,n) for(i=a;i<=n;++i)
#define for2(i,a,n) for(i=a;i<n;++i)
#define for3(i,a,n) for(i=a;i>=n;--i)
#define for4(i,a,n) for(i=a;i>n;--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define read(a) scanf("%d", &a)
#define print(a) printf("%d", a)
 
inline int getnum() {
    int ret=0; char c;
    for(c=getchar(); c<'0' || c>'9'; c=getchar());
    for(; c>='0' && c<='9'; c=getchar()) ret=ret*10+c-'0';
    return ret;
}
 
const int N=5005;
 
int imap[N][N];
int d[N], maxi[N];
 
int main() {
    int n, h, de, i, j, t, ans=0;
    n=getnum(); h=getnum(); de=getnum();
    for1(i, 1, n) {
        t=getnum();
        for1(j, 1, t)
            ++imap[getnum()][i];
    }
    for3(i, h, 1) {
        for1(j, 1, n) {
            d[j]=max(d[j], maxi[i+de])+imap[i][j];
            maxi[i]=max(maxi[i], d[j]);
        }
        ans=max(ans, maxi[i]);
    }
    print(ans);
    return 0;
}

【BZOJ】1270: [BeijingWc2008]雷涛的小猫（DP+水题）

Description

Input

Output

Sample Input

Sample Output

HINT

Source