變化序列

問題描述

對于這樣一串數字，他隻存在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;
    }
}