BZOJ 1270: [BeijingWc2008]雷涛的小猫

//尽管是水题也还是写到博客上吧。。。谁叫我太弱。。。难题都不会

Solution:

题目清晰…明示dp
一只猫可以从当前树上+1高度的位置,或是从其他树上当前高度+d的位置转移过来 求这只猫最多吃得到多少柿子。
按照题意写式子就好了 f[i][j]表示在第i棵树上,j高度时的最大收获 a[i][j]为第i棵树j高度的柿子数 可得
f[i][j] = max(f[i][j + 1], f[k][j + d]) + a[i][j]
这样k是需要枚举的 考虑优化
因为k是其他任意的一棵树 所以我们只需要记录一个mx[j]表示在所有树里选择j层可以获得的最大收获
显然这个mx[j + d] 取值如果和我们现在在同一棵树上 mx[j + d]是不会我们一直从f[i][j + 1]转移下来更优的,所以可以保证答案正确(来自tyk提醒)

Code:

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2001;
int n, h, d, nn, ans;
int a[N][N], f[N][N], mx[N];
inline int read() {
    int x = 0; bool w = 0; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') w = 1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return w ? - x : x;
}
int main() {
    n = read(), h = read(), d = read();
    for(int i = 1; i <= n; ++ i) {
        nn = read();
        for(int j = 1; j <= nn; ++ j) 
            ++ a[i][read()];
    }
    for(int i = 1; i <= n; ++ i)
    for(int j = 0; j < d; ++ j) {
        f[i][h - j] = f[i][h - j + 1] + a[i][h - j];
        mx[h - j] = mx[h - j] > f[i][h - j] ? mx[h - j] : f[i][h - j];
    }
    for(int j = h - d; j; -- j)
    for(int i = 1; i <= n; ++ i) {
        f[i][j] = max(f[i][j + 1], mx[j + d]) + a[i][j];
        mx[j] = mx[j] > f[i][j] ? mx[j] : f[i][j]; 
        ans = ans > f[i][j] ? ans : f[i][j];
    }
    printf("%d", ans);
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注