SRM502 Div1 Medium(500) TheProgrammingContestDivOne

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