题解 | #小红的华撃串#

考虑到字符串长度很小，且需要的子串数目为 ，设计动态规划状态为 代表着进行到第 个字符时， 且目前要求子串数目等于 的最小代价，转移时 的增加与减小取决于枚举下一个字符与当前字符是否一致（ 大于 的状态直接舍弃）， 值的增加取决于枚举的字符相较于原串是否发生改变，时间复杂度为 。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const LL maxn=550,inf=1LL<<62,M=1000000007;
LL n,m,ans=inf,a[maxn]={},f[maxn][2][6]={};
char s[maxn]={};
int main(){
	scanf("%lld",&n);scanf("%s",s+1);
	for(LL i=1;i<=n;i++)a[i]=s[i]-'0';
	for(LL p=0;p<=n;p++)for(LL i=0;i<2;i++)for(LL j=0;j<=3;j++)f[p][i][j]=inf;
	for(LL i=0;i<2;i++)
		for(LL j=0;j<2;j++)
			f[2][i][i^j]=min(f[2][i][i^j],(a[2]^i)+(a[1]^j));
	for(LL p=2;p<n;p++){
		for(LL i=0;i<2;i++){
			for(LL j=0;j<=3;j++){
				LL x=f[p][i][j];
				for(LL k=0;k<2;k++)
					f[p+1][k][j+(k^i)]=min(f[p+1][k][j+(k^i)],x+(k!=a[p+1]));
			}
		}
	}
	for(LL i=0;i<2;i++)ans=min(ans,f[n][i][3]);
	printf("%lld",ans);
	return 0;
}