簡單的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

?

轉載于:https://www.cnblogs.com/JSZX11556/p/4817733.html

總結

以上是生活随笔為你收集整理的BZOJ 1270: [BeijingWc2008]雷涛的小猫( dp )的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。