动态规划

$f(i, j)$ 表示小猫正在第 $i$ 棵树上的第 $j$ 层时 获得柿子的最大值

状态转移：小猫可以从 树的上一层下来 或者 其他树上跳下来

• 因此 $f(i, j) = max(f(i, j + 1), f(k, j + d)) + w(i, j) $, $1 <= k <= n$

朴素

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2010;

int n, h, d;
int w[N][N];
int f[N][N];

int main()
{
    cin >> n >> h >> d;

    for (int i = 1; i <= n; i ++ ) 
    {
        int cnt;
        cin >> cnt;
        while (cnt -- )
        {
            int j;
            cin >> j;
            w[i][j] ++ ;
        }
    }

    for (int j = h; ~j; j -- )
        for (int i = 1; i <= n; i ++ )
        {
            f[i][j] = f[i][j + 1] + w[i][j];
            for (int k = 1; k <= n; k ++ )
                f[i][j] = max(f[i][j], f[k][j + d] + w[i][j]);
        }

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[i][0]);

    cout << res;

    return 0;
}

上面 $ n^{3} $ 做法必然超时，然后发现第三层循环是找上面层的最大值， 用一个数组记录每层的最大值就可以了

AC 代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 4010;

int n, h, d;
int w[N][N];
int f[N][N], g[N];

int main()
{
    scanf("%d%d%d", &n, &h, &d);

    for (int i = 1; i <= n; i ++ ) 
    {
        int cnt;
        scanf("%d", &cnt);
        while (cnt -- )
        {
            int j;
            scanf("%d", &j);
            w[i][j] ++ ;
        }
    }

    for (int j = h; ~j; j -- )
        for (int i = 1; i <= n; i ++ )
        {
            f[i][j] = max(f[i][j + 1], g[j + d]) + w[i][j];
            g[j] = max(g[j], f[i][j]);
        }

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[i][0]);

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

    return 0;
}