SRM 533 Div2 Hard MagicalGirl

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11784&rd=14726
ある魔法少女は最初に非負整数Mのライフを持っている。毎日1ずつライフが減り、ライフ0で戦闘継続できなくなる。day[i]にモンスターに出会い、win[i]%の確率で勝利し、勝つことでgain[i]のライフを得る。もし負けたらそこで終わり。この少女が最大で生きられる日数を求めよ。

やりかた

Practice room のmamekinさんの答えを参考にしました。

メモ化再帰。敵に関する情報を敵が出現する早さ順にソートして深さ優先探索を行う。
以下ソース。

class MagicalGirl {
public:
  vector<vector<double> > memo;
  int Max;
  int N;
  vector<pair<int, pair<int, int> > > E;

  double rec(int d, int prevDay, int hp){
    if(d == N) return hp;
    if(memo[hp][d] > -EPS) return memo[hp][d];

    int day = E[d].first;
    double win = E[d].second.first / 100.0; 
    int gain = E[d].second.second; 
    
    int dlife = hp - (day - prevDay);
    if(dlife <= 0) return hp;
    
    double ret = 0;
    //出会った敵と戦う
                  //戦って勝つとき
    double ret = win * (rec(d + 1, day, min(Max, dlife + gain)) + (day - prevDay))
                  //戦って負けるとき
               + (1.0 - win) * (day - prevDay);
    //出会った敵と戦わない時との比較
    ret = max(ret, rec(d + 1, day, dlife) + (day - prevDay));
    
    return memo[hp][d] = ret;
  }
  double maxExpectation(int M, vector <int> day, vector <int> win, vector <int> gain) {
    double result;
    Max = M;
    N = day.size();
    E.clear();
    for(int i = 0; i < N; i++) E.push_back(make_pair(day[i], make_pair(win[i], gain[i])));
    sort(ALL(E));
    memo.assign(M + 1, vector<double>(N + 1, -1.0));
    return rec(0, 0, M);
  }
}

できてもいいはずなのに。