dp

状态

容易想到一个状态 $f(i,j)$ 表示前 $i$ 株玉米，进行 $j$ 次操作且第 $i$ 株玉米不拔掉最多剩多少株玉米。

转移

可以用暴力来枚举 $k,l$ 进行转移。

for (int k = 1; k < i; ++k)
	for (int l = 0; l <= j; ++l)
		if (a[k] + l <= a[i] + j) f[i][j] = max(f[i][j], f[k][l] + 1);

条件中的 $k<i$ 其实可以先不用管，看到 $l\le j,a_k+l\le a_i+j$ 明显是个二维的前缀和，于是就可以用二维的树状数组来维护。

#include <bits/stdc++.h>
using namespace std;
const int N = 10005;

int n, K, m, a[N], f[N][505], c[5505][505];

inline void add(const int &x, const int &y, const int &d) {
	for (int i = x; i <= m; i += i & ~i + 1)
		for (int j = y; j <= K + 1; j += j & ~j + 1) c[i][j] = max(c[i][j], d);
}
inline int ask(const int &x, const int &y) {
	int res = 0;
	for (int i = x; i; i &= i - 1)
		for (int j = y; j; j &= j - 1) res = max(res, c[i][j]);
	return res;
}

int main() {
	scanf("%d%d", &n, &K);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), m = max(m, a[i]); m += K;
	for (int i = 1; i <= n; ++i)
		for (int j = K; ~j; --j)//这里注意要倒着循环，因为小的j的更新会影响到大的。
			add(a[i] + j, j + 1, f[i][j] = ask(a[i] + j, j + 1) + 1);
	printf("%d", ask(m, K + 1));
	return 0;
}

时间复杂度 $O(nk\log k \log(k+\max a_i))$。其实这样就能 AC 了，但是还能优化。

可以发现在求二维前缀和时，每一行从左到右是单调不降的，每一列从上到下也是单调不降的。所以对于 $f(i,j)$ 最大值只会在第 $a_i+j$ 行和第 $j$ 列里，于是只用建一个 $k+\max a_i$ 行和一个 $k$ 行的一维树状数组记一下此行和此列的最大值进行更新转移就行了。

#include <bits/stdc++.h>
using namespace std;
const int N = 10005;

int n, K, m, a[N], c[2][5505][505];

inline void add(const int &x, const int &y, const int &d) {
	for (int i = x; i <= m; i += i & ~i + 1) c[0][i][y] = max(c[0][i][y], d);
	for (int i = y; i <= K + 1; i += i & ~i + 1) c[1][x][i] = max(c[1][x][i], d);
}
inline int ask(const int &x, const int &y) {
	int res = 0;
	for (int i = x; i; i &= i - 1) res = max(res, c[0][i][y]);
	for (int i = y; i; i &= i - 1) res = max(res, c[1][x][i]);
	return res;
}

int main() {
	scanf("%d%d", &n, &K);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), m = max(m, a[i]); m += K;
	for (int i = 1; i <= n; ++i)
		for (int j = K; ~j; --j)//这里正序倒序循环都没关系
			add(a[i] + j, j + 1, ask(a[i] + j, j + 1) + 1);
	printf("%d", ask(m, K + 1));
	return 0;
}

时间复杂度 $O(nk\log(k+\max a_i))$。