AtCoder ARC #010 : C - 積み上げパズル

さて３問目。
ARCはいつも３問目あたりで少しややこしいグラフ・DP系の問題を出してくるよね。
http://arc010.contest.atcoder.jp/tasks/arc010_3

ブロックの列が与えられ、それぞれを積み重ねるか重ねないかによってスコアが変わる。
また、コンボおよび全色利用のボーナスがつく。
そんななかスコアの最大値を求める問題。
見るからにDPで解く問題だね。

DPの状態として直前の色とこれまで利用した色のビットマスクを使う。
色の数は高々10なので、状態数は10*(2^10)、ブロックが5000個なので計算量は何とか持つ。

int N,M,Y,Z;
int bonus[26];
int ctoi[26];
ll dps[2][10][1024];

void solve() {
	int f,r,i,j,k,l;
	N=GETi();
	M=GETi();
	Y=GETi();
	Z=GETi();
	
	FOR(i,26) bonus['A'+i]=0;
	FOR(i,M) {
		char c[10];
		GETs(c);
		j=GETi();
		bonus[c[0]-'A']=j;
		ctoi[c[0]-'A']=i;
	}
	
	char str[10000];
	GETs(str);
	FOR(j,M) FOR(k,1<<M) dps[0][j][k]=dps[1][j][k]=-(1LL<<60);
	FOR(j,M) dps[0][j][0]=dps[1][j][0]=0;
	
	FOR(i,N) {
		int cur=i%2;
		int ne=1-i%2;
		int id=ctoi[str[i]-'A'];
		
		// no
		FOR(j,M) FOR(k,1<<M) dps[ne][j][k]=dps[cur][j][k];
		// yes
		FOR(j,M) FOR(k,1<<M) {
			ll sc=dps[cur][j][k]+bonus[str[i]-'A'];
			if(i>0 && j==id && (k&(1<<id))) sc+=Y;
			dps[ne][id][k|(1<<id)]=max(dps[ne][id][k|(1<<id)], sc);
		}
	}
	
	int cu=N%2;
	ll ma=-10000000000LL;
	FOR(j,M) {
		FOR(k,1<<M) {
			ll sc = dps[cu][j][k];
			if(k==(1<<M)-1) sc+=Z;
			ma=max(ma,sc);
		}
	}
	
	_P("%lld\n",ma);
}

まとめ

コンボだけなら単純なDPだけど、全色ボーナスで少し面白さが増しているね。