SRM502 Div1 Medium

500

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

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

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

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

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);
  }
};