AOJ Problem 0527 : Setting Go Stones

404 Not Found

最初に置く石の条件とか適当に付け加えてしまったせいで汚いソースになったけど方針としては、

同じ色で連続しているのを1つの要素にまとめる。

奇数番目だったら普通に置く。

(といっても、今の右端の色と同じだったらその要素に足すだけで、違ったら新しく要素追加して1にするんだけど)

違う色置こうとして、かつ偶数番目だったら、

右端の要素の個数+右端から1コ前の要素の個数 + 1(これから置くやつ)

を右端の要素として再編。

元の右端の要素はpop_back()されて、右端の1つ前だった要素(新しい右端)にその値が足されるイメージ。

黒を+,白を-の値にして扱った。

#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
	int n;
	while(cin >> n , n){
		int dp[100000] = {0};
		int pos = 0;
		rep(i,n){
			int c; cin >> c;
			if((i+1)%2 == 1){ //odd
				if(dp[pos] == 0){
					if(c)dp[pos]++; else dp[pos]--;
					continue;
				}
				if(c == 1 && dp[pos] > 0){
					dp[pos]++;
				}else if(c == 0 && dp[pos] < 0){
					dp[pos]--;
				}else{
					pos++;
					if(c == 1)dp[pos]++;
					else dp[pos]--;
				}
			}else{
				if(c == 1 && dp[pos] > 0){
					dp[pos]++;
				}else if(c == 0 && dp[pos] < 0){
					dp[pos]--;
				}else{
					if(pos == 0){
						dp[pos] *= -1;
					}else{
						dp[pos-1] -= dp[pos];
						dp[pos] = 0;
						pos--;
					}
					if(c == 1) dp[pos]++;
					else dp[pos]--;
				}
			}
		}
		int sum = 0;
		rep(i,100000){
			if(dp[i] < 0)sum += dp[i];
		}
		cout << -sum << endl;
	}
}