洛谷 P3287

不难发现一定是拔高一段后缀。

所以设 \(f_{i,j}\) 表示考虑前 \(i\) 个位置，拔高 \(j\) 次，第 \(i\) 个位置强制选的 LIS 的长度。

则有 \(f_{i,j}=\max\limits_{1\le x\lt i,0\le y\le j,a_x+y\le a_i+j}\left\{f_{x,y}+1\right\}\)。

\(x\lt i\) 天然满足，而剩下两个条件可以用二维 BIT 优化。

因为 \(j\) 可以为 \(0\) 所以要整体右移一位。

而且不难发现为了不让同一个 \(i\) 之间转移所以像背包一样 \(j\) 倒序枚举。

时间复杂度 \(\mathcal O(nk\log k\log w)\)，只能说非常离谱。

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 10005, M = 5005, K = 505;

void chkmax(int &a, int b) { if (a < b) a = b; }

int n, m;
int a[N], f[N][K], c[K][K+M];

void upd(int x, int y, int v) {
	for (int i = x; i <= m + 1; i += i & -i)
		for (int j = y; j <= 5500; j += j & -j) chkmax(c[i][j], v);
}

int query(int x, int y) {
	int res = 0;
	for (int i = x; i; i -= i & -i)
		for (int j = y; j; j -= j & -j) chkmax(res, c[i][j]);
	return res;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	for (int i = 1; i <= n; ++i)
		for (int j = m; ~j; --j)
			upd(j + 1, a[i] + j, f[i][j] = query(j + 1, a[i] + j) + 1);
	printf("%d", query(m + 1, 5500));
	return 0;
}