Codeforces 132 D. Constants in the language of Shakespeare

問題

二進数を、
a1+a2+…+amという形で表したい。
ただしここで、aiはすべて±2^xという形をしているものとする。

与えられた二進数を、上の形で表すために必要な最小の項の数および、
その和の形を具体的に一例出力せよ。

制約条件

二進数の桁数≦10^6

方針

DP+経路復元。

1が連続するところは引き算で作れる。
11111000 = 2^8 - 2^3のように。

今の桁を引き算で作っているか、足し算で作っているかのフラグと桁数を状態として、
dp[pos][flag]を、桁数までを作り、現在の状態が足し算or引き算で作っているときの最小コストとする。
これを更新していくO(n)のDPで解ける。

更新の仕方は下のような感じ。

足し算で作っているときは、1が出てきたら、1を足し算で作る（項数1）か、
引き算で作る（項数2）選ぶことができる。
足し算で作っているときに0が出てきたら、コスト0で作れる。

引き算で作っているときは、1が出てきたらコスト0で作れる。
もしくは、引き算で作っているのをコスト0で（最初に終了分のコストもとってあるので）終了することができる。
引き算で作っているときに0が出てきたら、コスト1かかる。

ソースコード

int dp[1000000][2],prev[1000000][2];

void run()
{
	string in; cin>>in;
	int n=in.size();
	rep(i,n+1)rep(j,2)dp[i][j]=inf;
	dp[0][0]=0;
	rep(i,n){
		if(in[i]=='1'){
			if(dp[i+1][1]>dp[i][1])dp[i+1][1]=dp[i][1],prev[i+1][1]=1;
			if(dp[i+1][0]>dp[i][1])dp[i+1][0]=dp[i][1],prev[i+1][0]=1;
			if(dp[i+1][1]>dp[i][0]+2)dp[i+1][1]=dp[i][0]+2,prev[i+1][1]=0;
			if(dp[i+1][0]>dp[i][0]+1)dp[i+1][0]=dp[i][0]+1,prev[i+1][0]=0;
		}
		else{
			if(dp[i+1][1]>dp[i][1]+1)dp[i+1][1]=dp[i][1]+1,prev[i+1][1]=1;
			if(dp[i+1][0]>dp[i][0])dp[i+1][0]=dp[i][0],prev[i+1][0]=0;
		}
	}
	int s=dp[n][0]>dp[n][1];
	cout<<min(dp[n][0],dp[n][1])<<endl;
	for(int i=n;i>0;i--){
		int p=prev[i][s];
		if(in[i-1]=='1'){
			if(p==1&&s==0)cout<<"-2^"<<n-i<<endl;
			if(p==0&&s==0)cout<<"+2^"<<n-i<<endl;
			if(p==0&&s==1)cout<<"+2^"<<n-i+1<<endl;
		}
		else{
			if(p==1&&s==1)cout<<"-2^"<<n-i<<endl;
		}
		s=p;
	}
}