Problem Statement
这题的描述比较复杂，就不说了。整个过程类似一个游戏，参数有天，生命值，胜利的概率，最后求最大存活的期望天数。
用dp[i][j]表示当前生命值为j，考虑了从i...N这些巫师的攻击。
有一点观察很重要，就是如果考虑巫师在同一天的话，那么安排他们的order与最后的结果是无关的，而对于每个巫师，要么攻击她，要么不攻击她。
还有一个要注意的是，巫师的状态决定了当天是那一天，而哪天并不能决定是哪个巫师，因此应该将巫师设为状态，而不应该是天。
由于下面的LP--后，后面忘了求的是原来的LP，导致最后的几个case wa掉了。
#include <iostream>#include <string>#include <vector>#include <algorithm>using namespace std;const double EPS = 1e-6;typedef pair<int, pair<int, int> > PIP;double dp[55][100005];bool cmp(PIP x, PIP y){return x.first < y.first;}class MagicalGirl{public: vector<PIP> witch;int LP_M;double go(int witchId, int LP) {int t_LP = LP;if(dp[witchId][LP] != -1) return dp[witchId][LP]; LP--;double res1, res2, res2_win, res2_lose;if(witchId + 1 == witch.size() || LP - witch[witchId + 1].first + witch[witchId].first <= 0) res1 = (witch[witchId].first + LP) * 1.0;else res1 = go(witchId + 1, LP - witch[witchId + 1].first + witch[witchId].first + 1);int gain = witch[witchId].second.second;int i_win = witch[witchId].second.first;double p_win = witch[witchId].second.first / 100.0;int M = min(LP_M, LP + gain);if(witchId + 1 == witch.size() || M - witch[witchId + 1].first + witch[witchId].first <= 0) res2_win = (witch[witchId].first + M) * 1.0;else res2_win = go(witchId + 1, M - witch[witchId + 1].first + witch[witchId].first + 1); res2_lose = witch[witchId].first; res2 = p_win * res2_win + (1 - p_win) * res2_lose;//res2 = (i_win * res2_win + (100 - i_win) * res2_lose) / 100.0; return dp[witchId][t_LP] = max(res1, res2); }double maxExpectation(int M, vector <int> d, vector <int> w, vector <int> g) { d.push_back(1); w.push_back(100); g.push_back(0);for(int i = 0; i < d.size(); i++) witch.push_back(make_pair(d[i], make_pair(w[i], g[i]))); sort(witch.begin(), witch.end(), cmp); LP_M = M;//fill(dp, -1, sizeof(dp)); for(int i = 0; i < 55; i++)for(int j = 0; j < 100005; j++) dp[i][j] = -1;return go(0, M); }};转载于:https://www.cnblogs.com/litstrong/archive/2012/02/26/2368557.html
