cf1204 D1. Kirk and a Binary String (easy version)

本文主要是介绍cf1204 D1. Kirk and a Binary String (easy version)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

hard version 的 On 做法我老早就看题解弄懂了，但 easy version 的 n2 暴力直到现在才想明白。。。

题意：

给定一个01串，尽量把1改成0，要求任意子区间的 LIS 长度保持不变。
这里的 LIS 为最长不降子列

串长2000

思路：

若把某个1改成0之后，以它为左端点的所有子区间的 LIS 长度保持不变，那就可以改。解释：

对某个固定的 \(L\)，把 \(s_L\) 从1改成0后 \(\forall R\in[L,n],\text{LIS}(L,R)\) 的长度不变 \(\iff \text{LIS}(L,R)\) 都是以1而非0开头 \(\iff\) 在 \([L,R]\) 中存在一个全1子列（11111），其长度严格大于任一 0011子列（修改 \(s_L\) 后，0011的长度最多和原来的11111相等）

考虑 \([p,R],p<L\) 的 \(\text{LIS}\) ，它的前半部分一定是区间 \([p,L-1]\) 的某个子列，后半部分要么是 \([L,R]\) 中的最长0011子列，要么是 \([L,R]\) 中的最长全1子列。由上段讨论，后半部分的长度不变，所以 \([p,R],p<L\) 的 \(\text{LIS}\) 长度也不变。

const signed N = 2003;
int n, f[N], g[N]; char s[N];

void LIS(int l, int *a) { //以l开头的所有子区间的LIS长度
    static int dp[2]; dp[0] = dp[1] = 0; //以0/1结尾的LIS长度
    for(int i = l; i <= n; i++) {
        if(s[i] == '0') dp[0]++;
        else dp[1] = max(dp[0], dp[1]) + 1;
        a[i] = max(dp[0], dp[1]);
    }
}

signed main() {
    iofast;
    cin >> s + 1; n = strlen(s + 1);
    for(int i = 1; i <= n; i++)
        if(s[i] == '1') {
            LIS(i, f);
            s[i] = '0'; LIS(i, g);
            for(int j = i; j <= n; j++) //比较
                if(f[j] != g[j]) s[i] = '1';
        }
    cout << s + 1;
}

这篇关于cf1204 D1. Kirk and a Binary String (easy version)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！