[题解] CF1858D Trees and Segments

· · 题解

为什么这个题能有 *2200 啊。。。

题目大意就是 01 序列翻转不超过 k 个，使得最长 0 的连续段长度 \times a 加上最长 1 的连续段长度最大。

考虑枚举最长 0 的连续段，记作 [l,r]，那么此时我们用的翻转次数就是 [l,r] 中 1 的个数，剩余的翻转次数记作 k'。那么此时我们需要在 [1,l-1] 或 [r+1,n] 中选一个区间 [l',r']，使得 [l',r'] 中 0 的个数 \le k' 且 r'-l'+1 最大。

记录 f_{i,j} 表示以 i 为起点的一段子串，满足 0 的个数 \le j 的最大长度。对于同一个 i，很显然 f_{i,j} 是满足单调性的，可以双指针求出。这部分复杂度 O(n^2)。

同理，记录 g_{i,j} 表示以 i 为结尾的一段子串，满足 0 的个数 \le j 的最大长度，用同样的方法可以 O(n^2) 求出。

那么当我们枚举了 [l,r] 作为 0 的连续段，这个 [l',r'] 的最大长度就是：

\max\{\max_{i=r+1}^n f_{i,k'},\max_{i=1}^{l-1} g_{i,k'}\}

我们对相同 j 的 f_{i,j},g_{i,j} 分别统计一个后缀 \max，前缀 \max 即可。

那么，此时我们就处理出了对于一个区间 [l,r] 作为 0 的连续段，最长的 1 的连续段的长度。此时我们可以处理出 ans_{i} 表示当 0 的连续段长度为 i 时，最长的 1 的连续段的长度，那么对于一个询问 a，其答案就是 \max\{a \cdot i+ans_i\}。

需要注意的细节：

时间复杂度 O(n^2)。

Code：

赛时用乱搞的号写的，代码会比较丑。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int t, n, k, a[3010], pre[3010][3010], suf[3010][3010], ans[3010], vis[3010];
char ch[3010];
signed main(){
    scanf ("%lld", &t);
    while (t --){
        scanf ("%lld%lld%s", &n, &k, ch+1);
        for (int i=1; i<=n; i++){
            a[i] = ch[i] - '0';
            ans[i] = vis[i] = 0;
        }
        a[n+1] = 0;
        for (int i=0; i<=k; i++) suf[n+1][i] = 0;
        for (int i=1; i<=n; i++){
            int now = 0, x = i-1;
            for (int j=0; j<=k; j++){//找i右边第j+1个0的位置，没有就是n+1
                while (now < j+1 && x <= n){
                    x ++;
                    if (a[x] == 0) now ++;
                }
                suf[i][j] = x - i;
            }
        }
        for (int i=n; i>=1; i--){
            for (int j=0; j<=k; j++){
                suf[i][j] = max(suf[i][j], suf[i+1][j]);
            }
        }
        for (int i=n; i>=1; i--){
            int now = 0, x = i+1;
            for (int j=0; j<=k; j++){
                while (now < j+1 && x >= 1){
                    x --;
                    if (a[x] == 0) now ++;
                }
                pre[i][j] = i - x;
            }
        }
        for (int i=1; i<=n; i++){
            for (int j=0; j<=k; j++){
                pre[i][j] = max(pre[i][j], pre[i-1][j]);
            }
        }
        vis[0] = 1;
        ans[0] = max(pre[n][k], suf[1][k]);
        for (int i=1; i<=n; i++){
            int tot = 0;
            for (int j=i; j<=n; j++){
                if (a[j] == 1) tot ++;
                if (tot > k) break;
                ans[j-i+1] = max(ans[j-i+1], suf[j+1][k-tot]);
                ans[j-i+1] = max(ans[j-i+1], pre[i-1][k-tot]);
                vis[j-i+1] = 1;
            }
        }
        for (int i=1; i<=n; i++){
            int now = 0;
            for (int j=0; j<=n; j++){
                if (!vis[j]) continue;
                now = max(now, i*j + ans[j]);
            }
            printf ("%lld ", now);
        }
        puts ("");
    }
    return 0;
}