TopCoder SRM 533 Div2 Hard MagicalGirl

このあたりは割と簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=11784

問題

魔法少女の初期ライフはMであり、1日ごとに1減少し、ライフが0になると死亡する。
ライフを回復するには、途中現れる魔女を倒さなければならない。

N人いる各魔女iはday[i]に1日だけ戦う機会があるが、戦っても戦わなくても良い。
戦った場合、win[i]の確率で勝利してライフがgain[i]回復する(ただし上限Mは超えない)。
負けた場合はその場で死亡する。

魔法少女が最適手を取った場合、生き延びれる日数の期待値を求めよ。

解法

魔女を登場日順にソートし、遠い順にDPしていく。
DPの状態としては、dp[魔女の番号][残りライフ]である。
各残りライフにおいて、魔女と戦った場合と戦わない場合の到達日数の期待値を求め、大きい方を取ればよい。
処理はO(NM)で終わる。

double dp[51][100010];

class MagicalGirl {
	public:
	double maxExpectation(int M, vector <int> day, vector <int> win, vector <int> gain) {
		int i,hp;
		int W=day.size();
		vector<pair<int, pair<double,int> > > V;
		
		FOR(i,W) V.push_back(make_pair(day[i],make_pair(win[i]/100.0,gain[i])));
		sort(V.begin(),V.end());
		reverse(V.begin(),V.end());
		ZERO(dp);
		
		FOR(hp,M+1) dp[0][hp]=V[0].first + max(hp+0.,min(M,hp+V[0].second.second)*V[0].second.first);
		for(i=1;i<W;i++) {
			for(hp=1;hp<=M;hp++) {
				int difd = (V[i-1].first-V[i].first);
				double nons = (difd>=hp)?(V[i].first+hp):dp[i-1][hp-difd];
				int nl=min(M,hp+V[i].second.second);
				double sel = (difd>=nl)?(V[i].first+nl):dp[i-1][nl-difd];
				dp[i][hp]=max(nons,sel*V[i].second.first+V[i].first*(1-V[i].second.first));
			}
		}
		if(V[W-1].first>=M) return M;
		return dp[W-1][M-V[W-1].first];
	}
};

まとめ

SRMは魔法少女が多すぎないですかね。