SRM 502 DIV1 medium TheProgrammingContestDivOne

topcoder

問題概要

50問の問題がある。
それぞれの問題について

  • 点数
  • 解くためにかかる時間
  • 1秒たつごとに減っていくその問題の点数

が与えられる。
使える時間T(最大100,000）が与えられる。
得られる点数を最大化せよ。

解法

貪欲＋DP
この問題の難しいところは、解いたときの時間で問題の点数が変わってしまうところである。
ここで、時間内にある問題の集合Pを解くことができるとする。
その場合、問題A問題Bが含まれていて、

  • 問題Aを解いてから問題Bを解く方が点数が高い場合
  • 問題Bを解いてから問題Aを解く方が点数が高い場合

の両方の可能性がある。
線形的に両問題の点数は減っていくことから、このAとBの関係はどのタイミングでABを解いても成り立つ。
つまり、最適な場合の解く問題順は、事前に上記の基準でソートした問題の全体列の部分列になる。
解く順番さえ決まっていれば、

  • 今何問目まで解くことを考慮したか。
  • 今どれだけ時間を使ったか。

を状態にして、その状態の点数を最大化するDPすることが可能。

ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
using namespace std;
typedef long long int lli;
class Data{
public:
  int r, p, id;
  bool operator<(const Data &d)const{
    return (double)r/p < (double)d.r/d.p;
  }
};
class TheProgrammingContestDivOne {
public:
  int find(int T, vector <int> maxPoints, vector <int> pointsPerMinute, vector <int> requiredTime) {
    int n = maxPoints.size();
    vector<Data> D(n);
    rep(i, n){
      D[i].r = requiredTime[i];
      D[i].p = pointsPerMinute[i];
      D[i].id = i;
    }
    sort(D.begin(), D.end());
    lli dp[100001];
    rep(i, 100001){
      dp[i] = 0;
    }
    rep(i, n){
      for(int j = T; j >= 0; j--){
        if(j + D[i].r > T)continue;
        lli time = j + D[i].r;
        lli score = maxPoints[D[i].id] - time * D[i].p;
        dp[time] = max(dp[time], score + dp[j]);
      }
    }
    return *max_element(dp, dp + T + 1);
  }
};