Codeforces #581 Div2 D2. Kirk and a Binary String (hard version)

またちょっとするとCodeforcesが空いてしまう…。
http://codeforces.com/contest/1204/problem/D2

問題

01で構成される文字列Sが与えられる。
以下の条件を満たす文字列Tのうち、1の数が最少の物を求めよ。

• Sの任意の部分列S[L...R]における単調増加な(不連続でもよい)部分列の最長なものは、T[L...R]におけるものと長さが同じ

解法

T=Sとし、後ろから順に1を0にできるか見ていこう。
今T[i]=1であるとき、T[i]=0になった場合と最長の部分列長を比べ変化が無ければ0にする。
最長の部分列長は、直前が0か1の場合に以後何要素取れるかの最大値を順次求めていけば埋められる。

int N;
string S;

int dpo[101010][2];
int dpp[101010][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	for(i=N-1;i>=0;i--) {
		S[i]-='0';
		if(S[i]==1) {
			dpo[i][0]=max(dpo[i+1][0],dpo[i+1][1]);
			dpo[i][1]=1+dpo[i+1][1];
		}
		else {
			dpo[i][0]=1+max(dpo[i+1][0],dpo[i+1][1]);
			dpo[i][1]=dpo[i+1][1];
		}
		if(S[i]) {
			if(1+max(dpp[i+1][0],dpp[i+1][1])==max(1+dpo[i+1][1],dpo[i+1][0])) {
				S[i]=0;
			}
		}
		if(S[i]==1) {
			dpp[i][0]=max(dpp[i+1][0],dpp[i+1][1]);
			dpp[i][1]=1+dpo[i+1][1];
		}
		else {
			dpp[i][0]=1+max(dpp[i+1][0],dpp[i+1][1]);
			dpp[i][1]=dpp[i+1][1];
		}
	}
	
	
	FOR(i,N) cout<<(int)S[i];
	
}

まとめ

この回全完多いなー。