No.107 モンスター - yukicoder
- bit dp の問題
- 最初 16! を 2^16 と勘違いして next_permutation を使ってしまって TLE。
- HP = 0 になってそれ以降の遷移がないケースを飛ばさずに WA してしまっていた。
class Monster {
public:
void solve(void) {
int N;
cin>>N;
vector<int> D(N);
REP(i,N)
cin>>D[i];
sort(RANGE(D));
vector<int> maxHP(1<<N, 100);
REP(bit,1<<N)
{
int cnt = 0;
REP(i,N) if (D[i] < 0 && (bit & (1<<i)) )
++cnt;
maxHP[bit] = 100*(cnt+1);
}
vector<int> dp(1<<N, 0);
dp[0] = maxHP[0];
REP(bit, 1<<N)
{
if (dp[bit] == 0)
continue;
REP(i,N)
{
if (bit & (1<<i))
continue;
int b = bit | (1<<i);
if (D[i] > 0)
dp[b] = min(max(dp[b], dp[bit]+D[i]), maxHP[b]);
else
dp[b] = max({dp[b], dp[bit]+D[i], 0});
}
}
cout<<dp[(1<<N)-1]<<endl;
}
};