SRM502 Div1 Medium(500) TheProgrammingContestDivOne
与えられたタスクを全て解く場合には、最も点数が高くなる順番は簡単に求められる。タスクが2つの場合に解く順番ごとの点数を求めると、pointsPerMinute[0]*requiredTime[1]>pointsPerMinute[1]*requiredTime[0]ならばタスク0から解けば良いことが分かる。タスクが3つ以上の場合も同様に、pointsPerMinuteとrequiredTimeの積を比較して並べた順番で解けば良い。
解く順番は分かるので、後は動的計画法でどのタスクを解くかを求める。
#include <vector> #include <algorithm> using namespace std; struct TASK { long long max, dec, time; TASK( int m, int d, int t ) { max=m, dec=d, time=t; } bool operator<(const TASK &t) const { return dec*t.time>t.dec*time; } }; class TheProgrammingContestDivOne{public: int find( int T, vector <int> maxPoints, vector <int> pointsPerMinute, vector <int> requiredTime ) { int n = maxPoints.size(); vector<TASK> task; for ( int i=0; i<n; i++ ) task.push_back(TASK(maxPoints[i],pointsPerMinute[i],requiredTime[i])); sort( task.begin(), task.end() ); // t秒で得られる点数の最大値 vector<long long> S( vector<long long>(T+1) ); for ( int i=0; i<n; i++ ) { vector<long long> P = S; for ( int j=0; j<=T; j++ ) { S[j] = P[j]; if ( j-task[i].time >= 0 ) S[j] = max( S[j], P[int(j-task[i].time)]+task[i].max-j*task[i].dec ); } } return (int)*max_element(S.begin(),S.end()); }};