Codeforces ECR #059 : E. Vasya and Binary String

今回は遅れて参加したのでまぁ順位は微妙。
http://codeforces.com/contest/1107/problem/E

問題

01で構成される文字列Sが与えられる。
ここから、同じ文字が連続している部分を取り除く、ということを繰り返す。
i文字を取り除いた場合、スコアとしてA[i]が加算されるとき、得られる総スコアの最大値を求めよ。

解法

以下をDPで解く。
dp(L,R,C,d) := S[L..(R-1)]から得られる最大スコアのうち、S[L]の直前に数値dがC個続いている場合のもの

状態遷移として以下のものが考えられる。

• C個続いた数値はここで打ち切ることにし、またS[L]を先頭とする部分文字列を考える。
  • この時A[d] + dp(L+1,R,1,S[L])が解の候補となる。
• C個続いた数値dに、次に同じ数値S[i]を連結するよう、S[L...(i-1)]を先に取り除く。
  • この時dp(L,i,0,0)+dp(i,R,C+1,d)が解の候補となる。

これで全体でO(N^4)となる。

int N;
string S;
int A[1010];
ll dp[101][101][101][2];

ll hoge(int L,int R,int con,int num) {
	if(R<=L) return A[con];
	
	if(dp[L][R][con][num]>=0) return dp[L][R][con][num];
	
	ll ret=-1;
	//stop
	ret=A[con]+hoge(L+1,R,1,S[L]);
	if(con) {
		for(int i=L;i<R;i++) if(S[i]==num) {
			ret=max(ret,hoge(L,i,0,0)+hoge(i+1,R,con+1,num));
		}
	}
	return dp[L][R][con][num]=ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(dp);
	cin>>N>>S;
	FORR(c,S) c-='0';
	FOR(i,N) cin>>A[i+1];
	cout<<hoge(0,N,0,0)<<endl;
}

まとめ

なんかTDPCのiwiと似たものを感じる。