天下一プログラマーコンテスト2012 決勝 : C Code Art Online

Cも解けた。
http://tenka1-2012-final.contest.atcoder.jp/tasks/tenka1_2012_final_c

問題の内容は上記問題文を参照。
これは２段階でDPをやればいいのかな。
まずプレイヤーのHPおよびBの連続した回数で状態を持つ。
HPは100までだし、Bは高々132あればよい(回復力が高くても100ターンあれば１撃で倒せるので、100+敵の数32ターン以上はかからない)ので状態数は100x132。

さらに、各敵ごとにこの100x132の状態の遷移を計算していく。
敵毎の状態はプレイヤーHP・敵HP・Bの連続数なので100x100x132。メモリも5MBで足りる。
これをDFSでA・B・C各パターンをとった場合で最短経路を求めていく。

この問題は大体O(HP^3×敵数)かな。敵の数が少ないので、あまり時間もかからない。

int N;
int HP,ATK,REC;
int DP[40][101];

int DP2[101][101][101];
int SDP[101][151],EDP[101][151];
deque<int> deq;

int key(int mhp,int ehp, int nb) {
	return mhp*40000+ehp*200+nb;
}
void do_dp2() {
	int x,y,z;

	MINUS(DP2);
	MINUS(EDP);
	deq.clear();
	FOR(x,101) {
		FOR(y,151) {
			if(SDP[x][y]==-1) continue;
			//わざわざ悪いのでやる必要はない
			for(z=x+1;z<=100;z++) if(SDP[z][y]!=-1 && SDP[z][y]<=SDP[x][y]) break;
			if(z<101) continue;
			for(z=y+1;z<=150;z++) if(SDP[x][z]!=-1 && SDP[x][z]<=SDP[x][y]) break;
			if(z<151) continue;
			DP2[x][HP][y] = SDP[x][y];
			deq.push_back(key(x,HP,y));
		}
	}
	
	while(!deq.empty()) {
		int mkey = deq.front();
		deq.pop_front();
		int myhp = mkey / 40000;
		int ehp = (mkey / 200)%200;
		int nb = mkey % 200;
		int turn = DP2[myhp][ehp][nb];
		//_P("%d -> %d %d %d %d\n",mkey,myhp,ehp,nb,turn);
		
		int nmhp,nehp;
		//Aを選択
		nmhp = myhp-ATK;
		nehp = ehp-5;
		if(nmhp > 0) {
			if(nehp<=0) {
				//撃破
				if(EDP[nmhp][0]==-1 || EDP[nmhp][0]>turn+1){
					//_P("A done! %d %d\n",nmhp,turn+1);
					EDP[nmhp][0]=turn+1;
				}
			}
			else {
				nehp += REC;
				if(nehp>HP) nehp=HP;
				if(DP2[nmhp][nehp][0]==-1 || turn+1<DP2[nmhp][nehp][0]) {
					DP2[nmhp][nehp][0]=turn+1;
					//_P("A : %d %d %d ->%d %d %d : %d (%d)\n",myhp,ehp,nb,nmhp,nehp,0,turn+1,key(nmhp,nehp,0));
					deq.push_back(key(nmhp,nehp,0));
				}
			}
		}
		
		//Bを選択
		nmhp = myhp-ATK;
		nehp = ehp-(nb+1);
		if(nmhp > 0) {
			if(nehp<=0) {
				//撃破
				if(EDP[nmhp][nb+1]==-1 || EDP[nmhp][nb+1]>turn+1){
					//_P("B done! %d %d %d\n",nmhp,nb+1,turn+1);
					EDP[nmhp][nb+1]=turn+1;
				}
			}
			else {
				nehp += REC;
				if(nehp>HP) nehp=HP;
				if(DP2[nmhp][nehp][nb+1]==-1 || turn+1<DP2[nmhp][nehp][nb+1]) {
					DP2[nmhp][nehp][nb+1]=turn+1;
					//_P("B : %d %d %d ->%d %d %d : %d (%d)\n",myhp,ehp,nb,nmhp,nehp,0,turn+1,key(nmhp,nehp,nb+1));
					deq.push_back(key(nmhp,nehp,nb+1));
				}
			}
		}
		//Cを選択
		nmhp = myhp-ATK;
		nehp = ehp;
		if(nmhp > 0) {
			nmhp += 50;
			if(nmhp>100) nmhp=100;
			nehp += REC;
			if(nehp>HP) nehp=HP;
			if(DP2[nmhp][nehp][0]==-1 || turn+1<DP2[nmhp][nehp][0]) {
				DP2[nmhp][nehp][0]=turn+1;
					//_P("C : %d %d %d ->%d %d %d : %d (%d)\n",myhp,ehp,nb,nmhp,nehp,0,turn+1,key(nmhp,nehp,0));
				deq.push_back(key(nmhp,nehp,0));
			}
		}
	}
	
}


void solve() {
	s64 res;
	int f,r,i,x,y,n,m,v1,v2;
	
	//combination
	N=GETi();
	
	MINUS(EDP);
	EDP[100][0]=0;
	FOR(i,N){
		GET3(&HP,&ATK,&REC);
		memmove(SDP,EDP,sizeof(SDP));
		do_dp2();
	}
	
	m=99999999;
	FOR(x,101) {
		FOR(y,151) {
			if(EDP[x][y]!=-1 && EDP[x][y]<m) m=EDP[x][y];
		}
	}
	if(m==99999999) m=-1;
	
	_P("%d\n",m);
	
}

まとめ

凡ミスで最初Bの回数を敵ごとに引き継がないと思っていてミスしてしまった。
とはいえ３回目のコミットでAC。
ここらへんの問題がミスがあったとはいえサックリ解けるようになるといい感じだね。