yukicoder : No.107 モンスター

最初アプローチを間違えてタイムロス。
http://yukicoder.me/problems/102

問題

主人公は初期状態で最大体力・体力ともに100である。

ここでN匹のモンスターがいる。

• 悪いモンスターを倒すと、モンスターごとの設定値D[i]分体力が減少するが、最大体力が100上昇する。
  • ただし、途中体力が0以下になるとゲーム終了である。
• 良いモンスターに出会うと、モンスターごとの設定値D[i]分体力が回復する。ただし最大体力は超えることがない。

各モンスターを倒すor出会える回数は１回だけである。
悪いモンスターを全部倒す場合、残る体力の最大値を求めよ。
ただし、途中で体力が0以下になりゲーム終了がしてしまった場合は0を答えよ。

解法

Nが小さいので、各敵を倒す/出会ったかどうかをbitmaskで管理し、BitDPで各状態に対する体力の最大値を更新していけば良い。
体力を回復する場合、最大体力が(1+今まで倒した悪い敵の数)*100となる点に気を付ける。

良いモンスターを余らせる意味はないので、全部の敵を倒す/出会った状態の体力を答えればよい。

int N;
int D[20];
int dp[1<<17];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>D[i];
	
	memset(dp,0xcf,sizeof(dp));
	dp[0]=100;
	FOR(i,1<<N) {
		if(dp[i]<0) continue;
		int did=1;
		FOR(j,N) if((i&(1<<j)) && D[j]<0) did++;
		FOR(j,N) if((i&(1<<j))==0) {
			if(D[j]>0) dp[i+(1<<j)]=min(did*100,max(dp[i+(1<<j)],dp[i]+D[j]));
			else if(dp[i]+D[j]>0) dp[i+(1<<j)]=max(dp[i+(1<<j)],dp[i]+D[j]);
		}
	}
	cout<<max(0,dp[(1<<N)-1])<<endl;
}

まとめ

最初悪いモンスターを設定値順ソートして、良いモンスターだけBitDPしてしまった。
サンプル４でだめだってわかるはずなのにね。