読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

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

ARC

さて3問目。
ARCはいつも3問目あたりで少しややこしいグラフ・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だけど、全色ボーナスで少し面白さが増しているね。

広告を非表示にする