codeforces D - Trees and Segments

思路

• 因为涉及到 $l_0$ 最大连续长度和 $l_1$ 最大连续长度，考虑枚举 $l_1$ 的长度 $dp{l}_0$ 的长度。
• $max0pref[i][cnt]$ 表示以 $i?1$ 结尾的 $l_0$
• $max0suf[i][cnt]$ 表示以 $i$ 开始的 $l_0$
• $max0by1[i]$ 表示 $l_1$ 为 $i$ 时最大的 $l_0$

计算

• $max0pref,max0suf$ 都是 $1\to 0$ ，所以记录 $cnt$ 更改次数

for(int i = 0; i < n; ++i) {
    int cnt = 0;
    for(int j = i; j <= n; ++j) {
        cnt += s[j - 1] == '1';
        max0pref[j][cnt] = max(max0pref[j][cnt], j - i);
        max0suf[i][cnt] = max(max0suf[i][cnt], j - i);
    }
}

更新

• $max0pre{f}_{i,j}=\{\begin{array}{l}max0pre{f}_{i?1,j}\\ max0pre{f}_{i,j?1}\end{array}$
• $max0su{f}_{i,j}=\{\begin{array}{l}max0su{f}_{i+1,j}\\ max0su{f}_{i,j?1}\end{array}$

for(int i = 0; i <= n; ++i) {
    for(int cnt = 0; cnt <= n; ++cnt) {
        if (i) max0pref[i][cnt] = max(max0pref[i][cnt], max0pref[i - 1][cnt]);
        if (cnt) max0pref[i][cnt] = max(max0pref[i][cnt], max0pref[i][cnt - 1]);
    }
}
for(int i = n; i >= 0; --i) {
    for(int cnt = 0; cnt <= n; ++cnt) {
        if (i + 1 <= n) max0suf[i][cnt] = max(max0suf[i][cnt], max0suf[i + 1][cnt]);
        if (cnt) max0suf[i][cnt] = max(max0suf[i][cnt], max0suf[i][cnt - 1]);
    }
}

更新 $max0by1$

• 每次选取一个区间，求当这个区间全为 $1$ 时的 $l_0$。

for(int i = 0; i < n; ++i) {
    int cnt=0;
    for(int j = i; j <= n; ++j) {
        if(j > i) cnt += s[j - 1] == '0';
        if(cnt > k) break;
        max0by1[j - i] = max(max0by1[j - i], max0pref[i][k - cnt]);
        max0by1[j - i] = max(max0by1[j - i], max0suf[j][k - cnt]);
    }
}

答案

• 按思路枚举 $l_1$ 长度即可

for(int i = 0; i <= n; ++i) {
    for(int a = 1; a <= n; ++a) ans[a] = max(ans[a], i + max0by1[i] * a);
}

Thick Twice, Code Once

#include<bits/stdc++.h>
#define il inline
#define get getchar
#define put putchar
#define is isdigit
#define int long long
#define dfor(i,a,b) for(int i=a;i<=b;++i)
#define dforr(i,a,b) for(int i=a;i>=b;--i)
#define dforn(i,a,b) for(int i=a;i<=b;++i,put(10))
#define mem(a,b) memset(a,b,sizeof a)
#define memc(a,b) memcpy(a,b,sizeof a)
#define pr 114514191981
#define gg(a) cout<<a,put(32)
#define INF 0x7fffffff
#define tt(x) cout<<x<<'\n'
#define ls i<<1
#define rs i<<1|1
#define la(r) tr[r].ch[0]
#define ra(r) tr[r].ch[1]
#define lowbit(x) (x&-x)
using namespace std;
typedef unsigned int ull;
typedef pair<int ,int > pii;
int read(void)
{
    int x=0,f=1;char c=get();
    while(!is(c)) (f=c==45?-1:1),c=get();
    while(is(c)) x=(x<<1)+(x<<3)+(c^48),c=get();
    return x*f;
}
void write(int x)
{
    if(x<0) x=-x,put(45);
    if(x>9) write(x/10);
    put((x%10)^48);
}
#define writeln(a) write(a),put(10)
#define writesp(a) write(a),put(32)
#define writessp(a) put(32),write(a)
const int N=1e6+10,M=3e4+10,SN=5e3+10,mod=998244353;
int n, k;
char s[N];
signed main()
{
    int T = read();
    while(T--)
    {
        n = read(), k = read();
        scanf("%s", s);
        vector<int > max0by1(n + 1,-INF);
        vector< vector<int > > max0pref(n + 1, vector<int >(n + 1));
        vector< vector<int > > max0suf(n + 1, vector<int >(n + 1));
        for(int i = 0; i < n; ++i) {
            int cnt = 0;
            for(int j = i + 1; j <= n; ++j) {
                cnt += s[j - 1] == '1';
                max0pref[j][cnt] = max(max0pref[j][cnt], j - i);
                max0suf[i][cnt] = max(max0suf[i][cnt], j - i);
            }
        }
        for(int i = 0; i <= n; ++i) {
            for(int cnt = 0; cnt <= n; ++cnt) {
                if (i) max0pref[i][cnt] = max(max0pref[i][cnt], max0pref[i - 1][cnt]);
                if (cnt) max0pref[i][cnt] = max(max0pref[i][cnt], max0pref[i][cnt - 1]);
            }
        }
        for(int i = n; i >= 0; --i) {
            for(int cnt = 0; cnt <= n; ++cnt) {
                if (i + 1 <= n) max0suf[i][cnt] = max(max0suf[i][cnt], max0suf[i + 1][cnt]);
                if (cnt) max0suf[i][cnt] = max(max0suf[i][cnt], max0suf[i][cnt - 1]);
            }
        }
        vector<int > ans(n + 1, -INF);
        for(int i = 0; i < n; ++i) {
            int cnt=0;
            for(int j = i; j <= n; ++j) {
                if(j > i) cnt += s[j - 1] == '0';
                if(cnt > k) break;
                max0by1[j - i] = max(max0by1[j - i], max0pref[i][k - cnt]);
                max0by1[j - i] = max(max0by1[j - i], max0suf[j][k - cnt]);
            }
        }
        for(int i = 0; i <= n; ++i) {
            for(int a = 1; a <= n; ++a) ans[a] = max(ans[a], i + max0by1[i] * a);
        }
        for(int i = 1; i <= n; ++i) writesp(ans[i]);
        puts("");
    }
    return 0;
}