前言
题目链接：洛谷。
题意简述
一个长为 \(n\) 的序列 \(\{a_n\}\) 和 \(q\) 次操作，第 \(i\) 次操作中，你可以删除序列长为 \(d_i\) 的前缀或后缀，并需要保证删除的所有数 \(\geq s_i\)。每次操作前，你可以选择任意长度的前缀或后缀，并将其删除，也可以不操作。请问，在你不能进行下一次操作前，你最多能执行多少次操作？
\(n \leq 5 \times 10^3\)，\(q \leq 2 \times 10^5\)。
题目分析
\(n\) 的范围提示我们考虑 \(\mathcal{O}(n^2)\)，进而发现 \(q\) 的范围在诈骗——至多进行 \(q\) 次操作后序列会被删空。所以，在算法开始前 \(q \gets \min \{n, q\}\)，让 \(n, q\) 同阶。
\(n, q\) 范围这么小，应该不是贪心，那就应该是 DP 了。我们很容易想到，\(f_{i, l, r}\) 表示在前 \(i\) 次操作后，能不能使序列只剩下 \([l, r]\)。边界显然是 \(f_{0, 1, n} = \text{true}\)，统计答案考虑第 \(i\) 次操作后，倘若 \(f_{i, l, r}\) 均为 \(\text{false}\)，则说明最多进行 \(i - 1\) 次操作。然后考虑转移。
转移其实就是进行某一次操作。找到一对使 \(f_{i-1,l,r}=\text{true}\) 的 \([l, r]\)，在这个区间上，我们尝试删去一段前缀或一段后缀。考虑前缀，后缀同理。我们枚举一个 \(k\)，表示删除 \([l, k-1]\) 后，满足 \(k+d-q\leq r\) 并且 \(\min\limits_{i=k}^{k+d-1}a_i \geq s\)，剩下区间为 \([k+d, r]\)。如果 \(k+d\gt r\)，则说明这次操作后会将序列删空，但是依然可以进行第 \(i\) 次操作。注意到，对于一对 \([l, r]\)，我们只需要转移最小的合法的 \(k\)，同样能进行一次操作的前提下，删的数越少明显不劣，这是一个常数优化。
其中，区间最小值可以在转移的时候用单调队列维护，但是没必要，\(\mathcal{O}(n^2)\) 预处理即可。上述算法的时间复杂度为 \(\Theta(qn^3)\)，需要优化。
遇到记录的是布尔值的 DP，往往有两种思考方向：使用 bitset 压位转移；考虑贪心后记录状态的最值。前者显然不适用本题，解释一下后者。对于具有相同左端点的区间 \([l, r_1]\) 和 \([l, r_2]\)，倘若均有 \(f_{i,l,r_1}=f_{i,l,r_2}=\text{true}\)，那么较大的那个 \(r\) 显然是不劣的，因为有更多的数保留下来，以后可能会用到。因此考虑舍弃原先的布尔值，使用 DP 记录最大的 \(r\)，即 \(f_{i,l}=r\) 表示在前 \(i\) 次操作后，能够使序列只剩下 \([l, r]\) 的最大的 \(r\)。
优化后，状态数由 \(\mathcal{O}(qn^2)\) 优化至 \(\mathcal{O}(qn)\)。考虑转移，记 \(\operatorname{mi}(l, r) := \min\limits _ {i=l}^r \{a_i\}\)。
- 当前使用前缀。\[f_{i,l} = \max \Big\{f_{i-1,k} \mid k\in[1,l-d] \land \operatorname{mi}(l-d+1,l-1) \geq s\Big\} \]
- 当前使用后缀。\[f_{i,l}=\max \Big\{r\mid\displaystyle r\in[l,f_{i-1,l}-d] \land \operatorname{mi}(r+1, r+d) \geq s\Big\} \]
朴素转移的话，时间是 \(\mathcal{O}(qn^2)\)。但是这个转移很有优化空间。第一种转移使用前缀最值优化即可；第二种转移翻译成人话，就是找到 \(\leq f_{i-1,l}\) 的最后一个位置，使得以其为结尾的长度为 \(d\) 的序列均 \(\geq s\)，于是可以预处理扫一遍，具体见代码。
于是时间可以优化至 \(\mathcal{O}(nq)\)，以及一些时空的常数优化，卡常后最优解。
代码
展开 $\mathcal{O}(qn^3)$ 代码
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 5010;
int n, q, a[N], _ = 1;
int mi[N][N];
bool f[N][N], g[N][N];
signed main() {
scanf("%d%d", &n, &q), q > n && (q = n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), mi[i][i] = a[i];
for (int l = 1; l <= n; ++l)
for (int r = l + 1; r <= n; ++r)
mi[l][r] = min(mi[l][r - 1], a[r]);
f[1][n] = true;
for (int sum = 0, d, s; _ <= q; ++_) {
scanf("%d%d", &d, &s), sum += d;
if (sum > n) break;
memcpy(g, f, sizeof(f));
memset(f, 0x00, sizeof(f));
bool ok = false;
for (int l = 1; l <= n; ++l)
for (int r = l + d - 1; r <= n; ++r)
if (g[l][r]) {
for (int k = l; k + d - 1 <= r; ++k)
if (mi[k][k + d - 1] >= s) {
f[k + d][r] = true;
ok = true;
break;
}
for (int k = r; k - d + 1 >= l; --k)
if (mi[k - d + 1][k] >= s) {
f[l][k - d] = true;
ok = true;
break;
}
}
if (!ok) break;
}
printf("%d", _ - 1);
return 0;
}
展开 $\mathcal{O}(qn^2)$ 代码
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 5010;
int n, q, a[N], _ = 1;
int mi[N][N];
int f[N], g[N];
signed main() {
scanf("%d%d", &n, &q), q > n && (q = n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), mi[i][i] = a[i];
for (int l = 1; l <= n; ++l)
for (int r = l + 1; r <= n; ++r)
mi[l][r] = min(mi[l][r - 1], a[r]);
f[1] = n;
for (int sum = 0, d, s; _ <= q; ++_) {
scanf("%d%d", &d, &s), sum += d;
if (sum > n) break;
memcpy(g, f, sizeof(f));
memset(f, -0x3f, sizeof(f));
for (int l = 1; l <= n; ++l) {
for (int r = l; r <= g[l] - d; ++r)
if (mi[r + 1][r + d] >= s)
f[l] = max(f[l], r);
if (l - d >= 1 && mi[l - d][l - 1] >= s)
for (int k = 1; k <= l - d; ++k)
f[l] = max(f[l], g[k]);
}
bool ok = false;
for (int i = 1; i <= n && !ok; ++i)
ok |= f[i] >= i - 1;
if (!ok) break;
}
printf("%d", _ - 1);
return 0;
}
展开 $\mathcal{O}(qn)$ 代码
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 5010;
int n, q, a[N], _ = 1, mi[N][N];
int f[N], g[N], p[N], h[N];
signed main() {
scanf("%d%d", &n, &q), q > n && (q = n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), mi[i][i] = a[i];
for (int l = 1; l <= n; ++l)
for (int r = l + 1; r <= n; ++r)
mi[l][r] = min(mi[l][r - 1], a[r]);
f[1] = n;
for (int sum = 0, d, s; _ <= q; ++_) {
scanf("%d%d", &d, &s), sum += d;
if (sum > n) break;
memcpy(g, f, sizeof(f));
for (int i = 1, c = 0; i <= n; ++i) {
p[i] = max(p[i - 1], g[i]);
a[i] >= s ? ++c : c = 0;
h[i] = c >= d ? i - d : h[i - 1];
}
for (int l = 1; l <= n; ++l) {
f[l] = -0x3f3f3f3f;
if (g[l] >= l && h[g[l]] >= l)
f[l] = max(f[l], h[g[l]]);
if (l - d >= 1 && mi[l - d][l - 1] >= s)
f[l] = max(f[l], p[l - d]);
}
bool ok = false;
for (int i = 1; i <= n && !ok; ++i)
ok |= f[i] >= i - 1;
if (!ok) break;
}
printf("%d", _ - 1);
return 0;
}
展开优化常数后 $\mathcal{O}(qn)$ 代码
#include <cstdio>
const int N = 5010;
int n, q, a[N], _ = 1;
int f[N], p[N], h[N];
inline void tomax(int &a, int &b) { b > a && (a = b); }
signed main() {
scanf("%d%d", &n, &q), q > n && (q = n), f[1] = n;
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int sum = 0, d, s; _ <= q; ++_) {
scanf("%d%d", &d, &s), sum += d;
if (sum > n) break;
for (int i = 1, c = 0; i <= n; ++i) {
p[i] = f[i] > p[i - 1] ? f[i] : p[i - 1];
a[i] >= s ? ++c : c = 0;
h[i] = c >= d ? i - d : h[i - 1];
}
bool ok = false;
for (int l = 1, c = 0; l <= n; ++l) {
int g = -0x3f3f3f3f;
if (f[l] >= l && h[f[l]] >= l)
tomax(g, h[f[l]]);
if (c >= d) tomax(g, p[l - d]);
a[l] >= s ? ++c : c = 0;
f[l] = g, ok |= g >= l - 1;
}
if (!ok) break;
}
printf("%d", _ - 1);
return 0;
}