BZOJ1270或洛谷1107 [BJWC2008]雷涛的小猫

BZOJ原题链接

洛谷原题链接

\(DP\)水题。
定义\(f[i][j]\)表示小猫在高度\(i\)，位于第\(j\)棵树时最多能吃到的柿子的数量。分为直接往下跳和跳到另一棵树两个决策。
那么很容易写出状态转移方程：
\[f[i][j] = \max \{ f[i + 1][j], f[i + Delta][k] \} + T[j][i]\]
注意到时间复杂度为\(O(n ^ 3)\)，太高。发现对于第二个决策，针对的高度都是相同的，再开一个数组记录每一高度下最多能吃到的柿子的数量，\(DP\)时直接调用并更新即可。
初始化全为\(0\)。
最后答案即为\(\max \{ f[1][j = 1 \to n] \}\)。
时间复杂度\(O(n ^2)\)。

#include<cstdio>
using namespace std;
const int N = 2010;
int f[N][N], T[N][N], ma[N];
inline int re()
{
    int x = 0;
    char c = getchar();
    bool p = 0;
    for (; c < '0' || c > '9'; c = getchar())
        p |= c == '-';
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    return p ? -x : x;
}
inline int maxn(int x, int y) { return x > y ? x : y; }
int main()
{
    int i, j, n, m, D, k;
    n = re(); m = re(); D = re();
    for (i = 1; i <= n; i++)
        for (k = re(), j = 1; j <= k; j++)
            T[i][re()]++;
    for (i = m; i; i--)
        for (j = 1; j <= n; j++)
        {
            f[i][j] = f[i + 1][j] + T[j][i];
            if (i + D <= m)
                f[i][j] = maxn(f[i][j], ma[i + D] + T[j][i]);
            ma[i] = maxn(ma[i], f[i][j]);
        }
    printf("%d", ma[1]);
    return 0;
}

BZOJ1270或洛谷1107 [BJWC2008]雷涛的小猫

原文：https://www.cnblogs.com/Iowa-Battleship/p/10492302.html