SRM 502 DIV1 Middle - TheProgrammingContestDivOne （復習xx）
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11357
プログラミングコンテストが開催され、複数与えられる問題を時間Ｔ以内に解く。
各問題について、得られるmaxPointsと1分あたりに引かれるポイント数pointsPerMinute、解くのに必要な時間requiredTimeが与えられる。
このとき、得られる最大のポイント数を求める。
解き方
問題を解く順番によりポイントが変わるのが問題文から読みとれる。
問題数は最大５０なので、50!とすると計算量が間に合わない。
ここで、各問題に与えられる情報からどの順番で問題を解けばよいかがわかる。
問題jを問題iより先に解いた方がスコアが高いのであれば、
maxp[i]-pm[i]*rtime[i]+maxp[j]-pm[j]*(rtime[i]+rtime[j])<
maxp[j]-pm[j]*rtime[j]+maxp[i]-pm[i]*(rtime[i]+rtime[j])
-pm[i]*rtime[i]-pm[j]*(rtime[i]+rtime[j])<-pm[j]*rtime[j]-pm[i]*(rtime[i]+rtime[j])
-pm[i]*rtime[i]-pm[j]*rtime[i]-pm[j]*rtime[j]<-pm[j]*rtime[j]-pm[i]*rtime[i]-pm[i]*rtime[i]
-pm[j]*rtime[i]<-pm[i]*rtime[i]
pm[j]*rtime[i]>pm[i]*rtime[i]
よってrequiredTime/pointsPerMinuteが大きい順に並び替え、
順にdpを適用していき最大のスコアを求めればよい。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class TheProgrammingContestDivOne {
public:
int find(int T, vector<int> maxp, vector<int> pm, vector<int> rtime) {
int n=maxp.size();
FORE(i,0,n){
FORE(j,i+1,n){
if((long long)pm[i]*rtime[j]<(long long)pm[j]*rtime[i]){
swap(maxp[i],maxp[j]);
swap(pm[i],pm[j]);
swap(rtime[i],rtime[j]);
}
}
}
int dp[100010]={};
FORE(i,0,n){
for(int t=min(T,maxp[i]/pm[i]);t>=rtime[i];t--){
dp[t]=max(dp[t],dp[t-rtime[i]]+maxp[i]-pm[i]*t);
}
}
int ret=0;
FORE(i,0,100010)ret=max(ret,dp[i]);
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class TheProgrammingContestDivOne {
public:
int find(int T, vector<int> maxp, vector<int> pm, vector<int> rtime) {
int n=maxp.size();
FORE(i,0,n){
FORE(j,i+1,n){
if((long long)pm[i]*rtime[j]<(long long)pm[j]*rtime[i]){
swap(maxp[i],maxp[j]);
swap(pm[i],pm[j]);
swap(rtime[i],rtime[j]);
}
}
}
int dp[100010]={};
FORE(i,0,n){
for(int t=min(T,maxp[i]/pm[i]);t>=rtime[i];t--){
dp[t]=max(dp[t],dp[t-rtime[i]]+maxp[i]-pm[i]*t);
}
}
int ret=0;
FORE(i,0,100010)ret=max(ret,dp[i]);
return ret;
}
};
