BZOJ 1270: [BeijingWc2008]雷涛的小猫( dp )

简单的dp..

dp(i,j) = max(dp(x,y))+cnt[i][j], (x,y)->(i,j)是合法路径.

设f(i)= max(dp(x,y))(1≤x≤N, 1≤y≤i), g(i,j) = max(dp(i, k))(1≤k≤j)

那么dp(i,j) =  max(f(j+delta), g(i,j+1))+cnt[i][j]. 递推即可. 时间复杂度O(NH)

-----------------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

const int maxn = 2009;

int N, H, delta, cnt[maxn][maxn];

int dp[maxn][maxn], f[maxn], g[maxn][maxn];

void init() {

scanf("%d%d%d", &N, &H, &delta);

memset(cnt, 0, sizeof cnt);

for(int i = 0; i < N; i++) {

int t; scanf("%d", &t);

while(t--) {

int h; scanf("%d", &h);

cnt[i][h]++;

}

}

}

void work() {

f[H] = 0;

for(int i = 0; i < N; i++)

   f[H] = max(f[H], dp[i][H] = g[i][H] = cnt[i][H]);

for(int h = H; --h; ) {

f[h] = f[h + 1];

   for(int i = 0; i < N; i++) {

    int t = g[i][h + 1];

    g[i][h] = t;

    if(h + delta <= H) t = max(t, f[h + delta]);

    dp[i][h] = t + cnt[i][h];

    f[h] = max(f[h], dp[i][h]);

    g[i][h] = max(g[i][h], dp[i][h]);

   }

}

int ans = 0;

for(int i = 0; i < N; i++)

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

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

}

int main() {

init();

work();

return 0;

}

-----------------------------------------------------------------------

1270: [BeijingWc2008]雷涛的小猫

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

Description

 

Input

Output

Sample Input

Sample Output

8

HINT

Source