SRM 502 Div1 500 TheProgrammingContestDivOne

問題概要
プロコンでは問題がn問出題される。
それぞれの問題に対して、

• point[i] 問題iを解いたときにもらえる得点
• minus[i] 問題iの単位時間あたりの得点の減衰
• time[i] 問題iを解くのに必要な時間

が与えられる。問題を解くのに使える時間はTである。
最適な戦略を用いたときに得られる得点の最大値を求めよ。

解法
この問題の面白いところは、

• 問題を解く順番の最適化
• 解くべき問題集合の最適化

という2つの最適化を考えなければいけないところ。

もし解く順序が分かっていれば0-1ナップサック問題に帰着できるので、順序を考える。

i=0,1,2,..,n-1の順で解くことを考えてみる。

このとき、

minus[k+1] * time[k] < minus[k] * time[k+1]

を満たさなければ、kとk+1の順序は逆にしたほうがいいことがわかる。

つまり問題を解く最適な順序は、

time[i] / minus[i]

が小さい順ということが分かる。

よって上の順でソートして、0-1ナップサック問題を解けばよい。

ソースコード

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

long long dp[100000+1];
class TheProgrammingContestDivOne {
public:
  int find(int T, vector<int> point, vector<int> minus, vector<int> time) {
    int n = point.size();

    // optimize order
    vector<pair<double, int> > vs;
    REP (i, n) vs.push_back(make_pair((double)time[i]/minus[i], i));
    sort(vs.begin(), vs.end());
    
    // optimize set
    memset(dp, 0, sizeof(dp));
    for (auto &pr: vs) {
      int i = pr.second;
      for (long long j = T; j >= time[i]; j--) {
        dp[j] = max(dp[j], dp[j-time[i]] + point[i] - minus[i] * j);
      }
    }
    return *max_element(dp, dp+T+1);
  }
};