比赛链接：https://vjudge.net/contest/405905#problem/D

题意：

给你一个长度为n的由0或1构成的串s，你需要切割这个串，要求切割之后的每一个子串长度要小于等于k。且每一个子串内不能全都是01交替，就比如

00101010、11010101这样没有问题，不需要切割，因为前面有两个相同的

01010101、10101010这样就不行，就必须切割开

问你最少需要切割多少次

题解：

我们设定输入的01串下标从1开始

我们使用dp[i]表示：s字符串的从第1个字符到第i个字符最少需要切割多少次

dp转移方程dp[i+j]=min(dp[i+j],dp[i-1]+1)

可以说我们使用dp[i-1]的值去维护后面dp的值，要保证[i,i+j]这一个子串不需要切割，且长度小于等于k

复杂度也就是O(n*k)，对于第一题是没问题的

AC代码：

1 #include

题解2（线段树+dp）：

但是我上面的dp方程无法优化，因为你要使用dp[i-1]的值去更新dp[i+j]的值，那么最坏情况也就是对于j(1<=j<=k)，dp[i-1]可以更新每一个dp[i+j]

那么最坏复杂度就是O(n*k)是无法优化的，所以要另辟蹊径

那我们可以把dp转移方程改成

dp[i]=min(dp[i-j]+1,dp[i])

可以说反转了一下，我们需要保证下标为[i-j+1,i]的子串不需要分割且长度小于等于k

那么我们可以使用线段树来维护所有dp[i]的值

对于dp[i]我们可以在线段树中查找区间[i-k,i-1]中的最小值就可以，但是因为题目要求分割后的子串中不能全部是01交替

所以我们查找区间[i-k,i-1]的最小值，我们需要找到以i为结尾，向左边找交替出现01的长度pre，就比如下面的串

0101101（下标从1开始）

i=7的话，如果k无限大，那么dp[i]就可以由dp[3]、dp[2]、dp[1]得到，因为下标4、5位置都是1，那么就说明如果对于变量j<4，那么子串[j+1,i]就可以满足题目要求

然后使用线段树找出来区间[i-k,i-pre]中的最小值就可以了

大致意思理解就可以，细节之处可以自己改一下，毕竟每一个人写的方式不一样

AC代码：

1 #include

题解3（双端队列维护）：

我们维护一个单调递增的队列，对于一个位置i，我们需要找到以i为结尾，向左边找交替出现01的长度pre

然后如果pre>k或者pre==i（pre==i表示串从头到i位置都是01交替）

那么dp[i]=dp[i-1]+1;

否则就从队列头部取出元素+1就是dp[i]的值

给你四个变量i、j、kk、l（i<j<kk<l，l-i<=k）

现在我们求dp[l]的值，如果dp[j]可以用来维护dp[l]（意味这子串[j+1,i]可以当成一个切割后的子串）。如果dp[kk]<dp[j]导致dp[j]被移出队列

那么也就意味着dp[j]无法维护dp[l]的值，这可以吗？

其实是可以的，因为如果dp[j]可以维护dp[l]那么dp[i]也是可以

且如果dp[i]在队列中，dp[i]<dp[j]，那么dp[j]丢失了也就没有关系了

代码：

#include
#include
#include
#include
#include

            if(pre==i || pre>=i-que\[start+1\])  
            {  
                dp\[i\]=dp\[que\[last\]\]+1;  
                //if(i==n)  
            }  
            else  
            {  
                dp\[i\]=dp\[que\[start+1\]\]+1;  
            }  
        }  
        while(start<last && dp\[i\]<dp\[que\[last\]\])  
            last--;  
        que\[++last\]=i;  
        //printf("%d ",dp\[i\]);  
    }  
    //printf("\\n");  
    printf("%d\\n",dp\[n\]-1);  
}  
return 0;  

}

/*
4
6 3
111000
5 2
11010
3 3
110
3 3
101

*/