题目大意:
可以证明每次操作的区间都是一段后缀。
设 $f[i][j]$ 表示操作 $j$ 次后以 $i$ 结尾的最长不下降子序列的长度,有
由于 $i$ 是从小到大枚举的,因此满足条件 $1 \leq k < i$,二维树状数组求最值,外层限制是 $l$,内层是 $a[k]+l$。
由于树状数组的第一层会有 $0$,整体加 $1$ 即可。
#include <cstdio>
int n, m, t, a[10005], b[505][5505], ans;
int read() {
int x = 0; char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x;
}
int max(int x, int y) {
return x > y ? x : y;
}
int lowbit(int x) {
return x & (-x);
}
void update(int x, int y, int z) {
for (int i = x; i <= m + 1; i += lowbit(i))
for (int j = y; j <= t; j += lowbit(j))
b[i][j] = max(b[i][j], z);
}
int query(int x, int y) {
int res = 0;
for (int i = x; i; i -= lowbit(i))
for (int j = y; j; j -= lowbit(j))
res = max(res, b[i][j]);
return res;
}
int main() {
n = read(), m = read();
for (int i = 1; i <= n; ++i) a[i] = read(), t = max(t, a[i]);
t += m;
for (int i = 1; i <= n; ++i) { //以i结尾
for (int j = m; j >= 0; --j) { //操作次数为j
int now = query(j + 1, a[i] + j) + 1;
ans = max(ans, now);
update(j + 1, a[i] + j, now);
}
}
printf("%d\n", ans);
return 0;
}