[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;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology