BZOJ原题链接

洛谷原题链接

\(DP\)水题。

定义\(f[i][j]\)表示小猫在高度\(i\)，位于第\(j\)棵树时最多能吃到的柿子的数量。分为直接往下跳和跳到另一棵树两个决策。

那么很容易写出状态转移方程：

注意到时间复杂度为\(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;

}