变化序列

问题描述

对于这样一串数字，他只存在0或者1，我们每次都能将一个0变成1又或者把一个1变成0，先需要我们将这串数字变成前半部分是0后半部分是1（或者全是0又或者全是1），至少我们需要变化多少次？

输入格式

第一行输入需要变化N串数字（1<=N<=30）

随后的N行输入该串的长度 以及串；(1<=length<=2*10000)

输出格式

每行输出最少变化次数（输出完后需要换行）

输入样例

2

10

1100011011

4

1101

输出样例

3

1

#include<iostream>
using namespace std;
#define N 200000
#define MIN 100000
int dp[N]={0};
int main()
{
    int n;
    cin>>n;
    while(n--){
        string s;
        int k,i,cnt,sum=0,min=MIN;
        cin>>k;
        cin>>s;
        dp[0]=0;
        for(cnt=0,i=0;i<k;i++){
            if(s[i]-'0'==cnt%2)
                dp[cnt]++;
            else{
                sum+=(cnt%2?0:dp[cnt]);
                cnt++;
                dp[cnt]=0;
                i--;
            }
        }
        sum+=(cnt%2?0:dp[cnt]);
        for(i=0;i<=cnt;i++){
            if(i%2)
                sum+=dp[i];
            else
                sum-=dp[i];
            if(sum<min)
                min=sum;
        }
        if(min==MIN)
            cout<<"0"<<endl;
        else
            cout<<min<<endl;
    }
}