SRM533 Div2 Hard

1000
メモ化する。
memo[N番目の魔女まで][残りライフ]

view plainprint?

1. const int N = 50 + 2;  
2. const int M = 100000 + 2;  
3. double memo[N][M];  
4.   
5. struct S {  
6.   double w;  
7.   int g;  
8.   int d;  
9.   S(double w_, int g_, int d_)  
10.     : w(w_), g(g_), d(d_) {};  
11. };  
12.   
13. vector<S> v;  
14.   
15. double rec(int nth, int m, int max_m)  
16. {  
17.   if (m <= 0) return v[nth].d + m;  
18.   if (nth == v.size()) return v.back().d + m;  
19.   if (memo[nth][m] < 0) ; else return memo[nth][m];  
20.   
21.   int next;  
22.   
23.   next = min(m + v[nth].g, max_m);  
24.   if (nth + 1 < v.size()) next -= v[nth + 1].d - v[nth].d;  
25.   double fight = 0;  
26.   fight += rec(nth + 1, next, max_m) * v[nth].w;  
27.   fight += v[nth].d * (1.0 - v[nth].w);  
28.   
29.   next = m;  
30.   if (nth + 1 < v.size()) next -= v[nth + 1].d - v[nth].d;  
31.   double ignore = rec(nth + 1,next, max_m);  
32.   
33.   return memo[nth][m] = max(fight, ignore);  
34. }  
35.   
36. bool cmp(S a, S b)  
37. {  
38.   return a.d < b.d;  
39. }  
40.   
41. class MagicalGirl {  
42. public:  
43.   double maxExpectation(int M, vector <int> D, vector <int> W, vector <int> G)  
44.   {  
45.     fill(&memo[0][0], &memo[N - 1][M], -1);  
46.   
47.     v.clear();  
48.     for (int i = 0; i < D.size(); ++i) {  
49.       v.push_back(S((double)W[i] / 100.0, G[i], D[i]));  
50.     }  
51.     sort(v.begin(), v.end(), cmp);  
52.   
53.     return rec(0, M - v[0].d, M);  
54.   }  
55. };  

const int N = 50 + 2;
const int M = 100000 + 2;
double memo[N][M];

struct S {
  double w;
  int g;
  int d;
  S(double w_, int g_, int d_)
    : w(w_), g(g_), d(d_) {};
};

vector<S> v;

double rec(int nth, int m, int max_m)
{
  if (m <= 0) return v[nth].d + m;
  if (nth == v.size()) return v.back().d + m;
  if (memo[nth][m] < 0) ; else return memo[nth][m];

  int next;

  next = min(m + v[nth].g, max_m);
  if (nth + 1 < v.size()) next -= v[nth + 1].d - v[nth].d;
  double fight = 0;
  fight += rec(nth + 1, next, max_m) * v[nth].w;
  fight += v[nth].d * (1.0 - v[nth].w);

  next = m;
  if (nth + 1 < v.size()) next -= v[nth + 1].d - v[nth].d;
  double ignore = rec(nth + 1,next, max_m);

  return memo[nth][m] = max(fight, ignore);
}

bool cmp(S a, S b)
{
  return a.d < b.d;
}

class MagicalGirl {
public:
  double maxExpectation(int M, vector <int> D, vector <int> W, vector <int> G)
  {
    fill(&memo[0][0], &memo[N - 1][M], -1);

    v.clear();
    for (int i = 0; i < D.size(); ++i) {
      v.push_back(S((double)W[i] / 100.0, G[i], D[i]));
    }
    sort(v.begin(), v.end(), cmp);

    return rec(0, M - v[0].d, M);
  }
};