CF1993D 题解

Register_int · 2024-08-05 00:49:45 · 题解

一眼二分答案，将序列中 <x 的数设为 -1，\ge x 的数设为 1。问题转化为：从序列中删掉 \lfloor\frac{n-1}m\rfloor 个长度为 m 的连续段，最大化剩下的值之和。

有个显然的 dp_{i,j} 表示前 i 个数删了 j 段的最优解，但是状态数 O(n^2) 无法接受。但发现 j 必须要 \ge\lfloor\frac{i-1}m\rfloor，同时它又 \le\lfloor\frac im\rfloor。也就是说，对于每个 i，有用的 j 只有两个。

修改状态 dp_{i,j=0/1} 表示前 i 格分了 \lfloor\frac{i-1}m\rfloor+j 段的最优解，记忆化搜索转移，时间复杂度 O(n\log V)。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e6 + 10;

int T, n, m, a[MAXN], b[MAXN], dp[MAXN][2]; bool vis[MAXN][2];

int dfs(int x, int k) {
    if (x < 0 || k < 0 || m * k > x) return -1e9;
    if (!x) return 0; int t = k - (x - 1) / m;
    if (vis[x][t]) return dp[x][t]; vis[x][t] = 1;
    return dp[x][t] = max(dfs(x - 1, k) + b[x], dfs(x - m, k - 1));
}

inline 
bool check(int x) {
    for (int i = 1; i <= n; i++) b[i] = (a[i] >= x ? 1 : -1);
    for (int i = 1; i <= n; i++) vis[i][0] = vis[i][1] = 0;
    return dfs(n, (n - 1) / m) > 0;
}

int l, r, mid;

int main() {
    for (scanf("%d", &T); T--;) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (l = 1, r = 1e9; l < r; check(mid = l + r + 1 >> 1) ? l = mid : r = mid - 1);
        printf("%d\n", l);
    }
}