SRM502 Div1 Medium

500

貪欲 & DP
DPか貪欲だろうとは雰囲気で察することができた。
が、具体的な解法が思いつかない。試しに問題からでなく上限から解法を考えてみる。

入力の上限から、( 時間 * 問題数 ) くらいの計算はできそうなので、それを足がかりに DP を考える。
DP[どの問題まで][経過時間] ならできそう。

こうなると、解く順番が問題。
解く問題が決まるということは、ポイントの総和が決まるということ。
なら、解く順番は減少が少なくなるように決めるはず。

( 減少 / 消費時間 ) でソートして試す。サンプル合う。通る。

view plainprint?

1. struct S {  
2.   lli mx;  
3.   lli minus;  
4.   lli req;  
5.   S (int m, int mi, int r) : mx(m), minus(mi), req(r) {}  
6. };  
7.   
8. bool f(S a, S b)  
9. {  
10.   return ((double)a.minus / a.req) > ((double)b.minus / b.req);  
11. }  
12.   
13. class TheProgrammingContestDivOne {  
14. public:  
15.   int find(int T, vector <int> mx, vector <int> minus, vector <int> req)  
16.   {  
17.     const int N = mx.size();  
18.     vector<S> v;  
19.     for (int i = 0; i < N; ++i) {  
20.       v.push_back(S(mx[i], minus[i], req[i]));  
21.     }  
22.     sort(v.begin(), v.end(), f);  
23.   
24.     const int M = 50 + 5;  
25.     const int L = 100000 + 5;  
26.     static lli dp[M][L];  
27.     fill(&dp[0][0], &dp[M - 1][L - 1] + 1, 0);  
28.     for (lli i = 0; i < N; ++i) {  
29.       for (lli j = 0; j <= T; ++j) {  
30.         int ni = i + 1;  
31.         int nj = j + v[i].req;  
32.         lli point = v[i].mx - (v[i].req + j) * v[i].minus;  
33.         if (0 <= point && nj <= T) {  
34.           dp[ni][nj] = max(dp[ni][nj], dp[i][j] + point);  
35.         }  
36.         dp[ni][j] = max(dp[ni][j], dp[i][j]);  
37.       }  
38.     }  
39.     return *max_element(&dp[0][0], &dp[M - 1][L - 1] + 1);  
40.   }  
41. };  

struct S {
  lli mx;
  lli minus;
  lli req;
  S (int m, int mi, int r) : mx(m), minus(mi), req(r) {}
};

bool f(S a, S b)
{
  return ((double)a.minus / a.req) > ((double)b.minus / b.req);
}

class TheProgrammingContestDivOne {
public:
  int find(int T, vector <int> mx, vector <int> minus, vector <int> req)
  {
    const int N = mx.size();
    vector<S> v;
    for (int i = 0; i < N; ++i) {
      v.push_back(S(mx[i], minus[i], req[i]));
    }
    sort(v.begin(), v.end(), f);

    const int M = 50 + 5;
    const int L = 100000 + 5;
    static lli dp[M][L];
    fill(&dp[0][0], &dp[M - 1][L - 1] + 1, 0);
    for (lli i = 0; i < N; ++i) {
      for (lli j = 0; j <= T; ++j) {
        int ni = i + 1;
        int nj = j + v[i].req;
        lli point = v[i].mx - (v[i].req + j) * v[i].minus;
        if (0 <= point && nj <= T) {
          dp[ni][nj] = max(dp[ni][nj], dp[i][j] + point);
        }
        dp[ni][j] = max(dp[ni][j], dp[i][j]);
      }
    }
    return *max_element(&dp[0][0], &dp[M - 1][L - 1] + 1);
  }
};