原题链接
数据结构优化DP
前置知识：二维树状数组 e.g.https://www.luogu.com.cn/problem/P4514
思路如下：
代码如下：
#include <cstdio>
#include <cctype>using namespace std; inline int read() {int x = 0, f = 0; char ch = getchar(); while (!isdigit(ch)) f = ch == '-', ch = getchar(); while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar(); return f ? -x : x;
}inline void print(int x) {if (x < 0) putchar('-'), x = -x;if (x < 10) putchar(x + '0');else {print(x / 10); putchar(x % 10 + '0');}
}const int N = 2050;
int n, m;
int tr[4][N][N]; void addtr(int type, int x, int y, int k) {for (int i = x; i < N; i += (i & -i)) {for (int j = y; j < N; j += (j & -j)) {tr[type][i][j] += k; }}
}int asktr(int type, int x, int y) {int res = 0; for (int i = x; i > 0; i -= (i & -i)) {for (int j = y; j > 0; j -= (j & -j)) {res += tr[type][i][j]; }}return res;
}void add(int x, int y, int k) {addtr(0, x, y, k); addtr(1, x, y, k * y); addtr(2, x, y, k * x); addtr(3, x, y, k * x * y);
}int ask(int x, int y) {return asktr(0, x, y) * (x * y + y + x + 1) - asktr(1, x, y) * (x + 1) - asktr(2, x, y) * (y + 1) + asktr(3, x, y);
}int main() {scanf("X %d %d", &n, &m); char opt; int aa, bb, cc, dd, kk; while (~scanf("%s",&opt)) {scanf("%d%d%d%d", &aa, &bb, &cc, &dd);if (opt == 'L') {scanf("%d", &kk); add(aa, bb, kk); add(aa, dd + 1, -kk); add(cc + 1, bb, -kk); add(cc + 1, dd + 1, kk); } else {print(ask(cc, dd) - ask(aa - 1, dd) - ask(cc, bb - 1) + ask(aa - 1, bb - 1)); putchar('\n'); }}return 0;
}
回到本题，
f[i,j]表示以i为结尾，i位置提升j次的最长单调不下降序列，则有：
f[i,j] = max{f[k,l]} + 1, 1 <= k < i, 0 <= l <= j, h[i] + j >= h[k] + l，
考虑滚动数组省去一维，可有h[i] + j >= h[k] + l的限制，则针对该限制再加一维，
f[j, k]表示以i为结尾，提升后高度为j， i位置提升k次的最长单调不下降序列，则有：
j = h[i] + k, f[j,k] = max{f[l,m]} + 1, 1 <= l <= j, 0 <= m <= k,
考虑二维树状数组优化，由于第二维可取0，则整体加1，
代码如下：
#include <cstdio>
#include <cctype>
#include <algorithm>using namespace std; inline int read() {int x = 0, f = 0; char ch = getchar(); while (!isdigit(ch)) f = ch == '-', ch = getchar(); while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar(); return f ? -x : x;
}inline void print(int x) {if (x < 0) putchar('-'), x = -x;if (x < 10) putchar(x + '0');else {print(x / 10); putchar(x % 10 + '0');}
}const int N = 10010, L = 5010, K = 510;
int n, k, ans, a[N], tr[L + K][K]; void update(int x, int y, int kk) {for (int i = x; i < L + K; i += i & -i) {for (int j = y; j < K; j += j & -j) {tr[i][j] = max(tr[i][j], kk); }}
}int find(int x, int y) {int res = 0; for (int i = x; i > 0; i -= i & -i) {for (int j = y; j > 0; j -= j & -j) {res = max(res, tr[i][j]); }}return res;
}int main() {n = read(); k = read(); for (int i = 1; i <= n; ++i) {a[i] = read(); } for (int i = 1; i <= n; ++i) {for (int j = k; j >= 0; --j) {int x = find(a[i] + j, j + 1) + 1; ans = max(ans, x); update(a[i] + j, j + 1, x); }}print(ans); return 0;
}
