比赛链接：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
*/
