题目描述

blablabla

样例

输入样例：
3 10 2
3 1 4 10
6 3 5 9 7 8 9
5 4 5 3 6 9
输出样例：
8

算法1

(动态规划)

根据题题目描述构造状态，f[j][i]:高度为j，树的编号为i时所有的柿子最大数量,根据题目的描述可以得出状态转移方程：f[j][i]=max(f[j][i], f[j-δ][k]/f[j-1][k]),当k!=i时取f[j-δ][k],当k==i时取f[j-1][k]。
所以可以得到朴素的写法，根据当前高度，枚举j-δ高度的所有树有的柿子数量，如代码一。
但是发现，更新当前状态，只关心j-δ高度N颗树中的最大值，所以可以去掉枚举，而是新增一个数组记录每一个高度下所具备的果子最大数量用于更新后继的状态，如代码二所示。

朴素写法

#include <iostream>
#include <cstring>
using namespace std;

const int maxn = 2010;

int N, H, D;
int h[maxn][maxn];//第一维树的高度，第二维树的编号
int f[maxn][maxn];


int solve() {
    memset(f, 0, sizeof(f));

    for (int j = 1; j <= H; j++) {
        for (int i = 1; i <= N; i++) {//枚举每一颗树
            f[j][i] = f[j - 1][i];
            for (int k = 1; k <= N; k++) {//枚举上一个颗树
                if (k != i && j - D >= 0) {
                    f[j][i] = max(f[j][i], f[j - D][k]);
                }
            }
            f[j][i] += h[j][i];//加上自己位置的果子数量
        }
    }

    int ans = 0;
    for (int i = 1; i <= N; i++) {
        ans = max(ans, f[H][i]);
    }

    return ans;
}


int main() {
    int nums, hh;

    scanf("%d%d%d", &N, &H, &D);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &nums);
        for (int j = 1; j <= nums; j++) {
            scanf("%d", &hh);
            h[H + 1 - hh][i]++;
        }
    }

    int ans = solve();
    printf("%d\n", ans);

    return 0;
}

增加最大值数组写法

#include <iostream>
#include <cstring>
using namespace std;

const int maxn = 2010;

int N, H, D;
int h[maxn][maxn];//第一维树的高度，第二维树的编号
int cnts[maxn];//记录每一个高度下所拥有的最大果子数目
int f[maxn][maxn];


int solve() {
    memset(f, 0, sizeof(f));

    for (int j = 1; j <= H; j++) {
        for (int i = 1; i <= N; i++) {//枚举每一颗树
            f[j][i] = f[j - 1][i];
            if (j - D >= 0) {
                f[j][i] = max(f[j][i], cnts[j - D]);
            }
            f[j][i] += h[j][i];//加上自己位置的果子数量
            //更新当前高度下最大果子数量
            cnts[j] = max(cnts[j], f[j][i]);
        }
    }

    int ans = 0;
    for (int i = 1; i <= N; i++) {
        ans = max(ans, f[H][i]);
    }

    return ans;
}


int main() {
    int nums, hh;

    scanf("%d%d%d", &N, &H, &D);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &nums);
        for (int j = 1; j <= nums; j++) {
            scanf("%d", &hh);
            h[H + 1 - hh][i]++;
        }
    }

    int ans = solve();
    printf("%d\n", ans);

    return 0;
}