Codeforces #171 Div2. E. Beautiful Decomposition

さてようやく最終問題。
http://codeforces.com/contest/279/problem/E

問題

最大10^6桁の２進数が与えられる。
この数字を２の累乗の加減算で表現するとき、必要な２の累乗数の最小数を答える。

解法

下の位からDPで処理していく。
繰り上がりと各桁の和が1になる場合、その桁で加算または減算が１回必要となる。
そこで加算の場合と減算の場合をそれぞれDPで処理すればよい。

int L;
char S[1000003];

void solve() {
	int f,r,i,j,k,l,x,y,cur,tar;
	int ma=0;
	
	GETs(S);
	L=strlen(S);
	reverse(S,S+L);
	
	int dp[2][2];
	ZERO(dp);
	dp[0][1]=9999999;
	
	FOR(i,L-1) {
		cur=i%2;
		tar=1-cur;
		
		if(S[i]=='0') {
			// minus
			dp[tar][0]=min(dp[cur][0], 1+dp[cur][1]);
			//add
			dp[tar][1]=1+dp[cur][1];
		}
		else {
			// add
			dp[tar][1]=min(dp[cur][1], 1+dp[cur][0]);
			// minus
			dp[tar][0]=1+dp[cur][0];
		}
	}
	
	if(L==1) _P("1\n");
	else _P("%d\n",1+min(dp[tar][0],dp[tar][1]));
	
	return;
}

まとめ

一見ややこしいけど、意外と単純な問題。