Submission #66357928

---

Source Code Expand

#include<iostream>
#include<vector>
using namespace std;
using P = pair<int,int>;
void solve(){
	int N;cin>>N;
	vector<P> rl;
	string S;cin>>S;
	for(int i=0;i<N;++i){
		if(rl.size()!=0 && rl.back().first == S[i]-'0'){
			rl.back().second++;
		} else {
			rl.emplace_back(S[i]-'0',1);
		}
	}

	int M = rl.size();
	int count = 0;
	for(int i=0;i<M;++i){
		if(rl[i].first==1)count+=rl[i].second;
	}

	int INF = 1<<30;
	vector<vector<long long>> dp(M+1,vector<long long>(3,INF));
	dp[0][0] = dp[0][1] = dp[0][2] =  0;
	for(int i=0;i<M;++i){
		if(rl[i].first==0){
			dp[i+1][0] = min(dp[i+1][0],dp[i][0]);
			dp[i+1][2] = min(dp[i+1][2],dp[i][0]+rl[i].second);
			dp[i+1][2] = min(dp[i+1][2],dp[i][2]+rl[i].second);
			dp[i+1][1] = min(dp[i+1][1],dp[i][2]);
		}
		if(rl[i].first==1) {
			dp[i+1][0] = min(dp[i+1][0],dp[i][0]+rl[i].first);
			dp[i+1][1] = min(dp[i+1][1],dp[i][1]+rl[i].first);
			dp[i+1][2] = min(dp[i+1][2],dp[i][0]);
		}
	}

	cout << min(min(dp[M][0],dp[M][1]),dp[M][2]) << endl;
	
}

int main(){
	int T;cin>>T;
	for(;T--;){
		solve();
	}
}

Submission Info

Judge Result