[TIOJ] 1853 . Ch1-1.一切的開始

題目連結:http://tioj.infor.org/problems/1853

---

本題似乎有DP作法，狀態可能是什麼，強制把前i個都轉成0跟1的方法數。不過，其實也可以greedy做，準則是:從右邊面看到左邊時，若看到一個0，則看其左邊是否也為0，若是的話就用翻的，反之則用點的。因為對於一個XXXXX101111的序列，若在0那點用翻的，則會將下一個一變成0，那必定之後又要用翻的，最後會變成XXXXX111111，花費兩個操作，但是用點的只要一個操作；另外一方面，對於一個XXXXX001111，如果都用點的，需花費兩操作，但是如果用翻的最多也是兩操作，並不會比較慘。

#include <bits/stdc++.h>
using namespace std;
#define N 10000000

char arr[N+5];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;cin>>n>>arr;
	int ans=0;
	bool cur=0;
	for(int i=n-1;i>=1;i--){
		if(arr[i]=='0'+cur){
			ans++;
			if(arr[i]==arr[i-1]) cur=!cur;
		}
	}
	if(arr[0]=='0'+cur) ans++;
	cout<<ans<<'\n';
	return 0;
}