Codeforces Round #646 (Div. 2) B. Subsequence Hate

题目传送门: Codeforces.

题目大意：

给定一个由0和1组成的字符串s,有一种改动字符串的方式：1->0，0->1。问最少通过多少次改动可以使字符串s不包含字串”010“和”101“。本题中字串的意思是如果字符串b可以删除几个字符得到字符串a，那么a就是b的字串。

思路：

不难思考，满足题目要求的字串只有2种方式： 第一种：字符串全为0或1； 第二种：字符串分为两段，前一段为0或1，后一段为前一段相反，如000111，110000。 所以我们只需要从前向后一次划分，找出最小的改动次数即可。

代码如下：

#include <bits/stdc++.h> using namespace std; #define ll long long const int Max=1e6+7; char s[1005]; int sum0[1005],sum1[1005]; // sum0[i]表示从0到i有多少个‘0’; int tot0[1005],tot1[1005]; // tot0[i]表示从最后一位到i有多少个‘0’; int main(){ int T; scanf("%d",&T); while(T--){ scanf("%s",&s); int len=strlen(s); int count0 =0,count1 =0; int ans=1005; for(int i=0; i<len; i++){ if(s[i]=='0') count0++; else count1++; sum0[i]=count0; sum1[i]=count1; } ans=min(count0,count1); //字符串全为0或1的较小值 count0=count1=0; for(int i=len-1; i>=0; i--){ if(s[i]=='0') count0++; else count1++; tot0[i]=count0; tot1[i]=count1; } //0到i全为1，改动次数为i+1-sum0[i]，i到最后全为0， //len-i-1-tot1[i+1],所以改动次数为两者相加 len-sum0[i]-tot1[i+1]。 for(int i=0; i<len-1; i++){ ans=min(ans,len-sum0[i]-tot1[i+1]); //前段为1，后段为0. ans=min(ans,len-sum1[i]-tot0[i+1]); //前段为0，后段为1 } printf("%d\n",ans); } return 0; }