問題
http://topcoder.bgcoder.com/print.php?id=1405
複数のプログラミングコンテストが開催され、各コンテストについて開始時間s、終了時間t、勝率pが与えられる。
プレイヤーはできるだけ多くのコンテストで勝ちを収めたい。ただし、時間が重複しているコンテストには出ることができない。
このとき、最も勝ちを収めることができたときの勝数を求める。
解き方
サンプルを見ると、重複していない限りはできるだけ多くのコンテストに出場した方がよいことがわかる。
開始時間でソートし、該当コンテストにおいて最も勝数が高い場合は、その一つ前までの最適な勝数がわかっていれば求めることができる。
これを利用して、漸化式でｄｐを解く。
コード
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 ContestSchedule {
public:
double expectedWinnings(vector<string> contests) {
int n=contests.size();
vector<pair<int,pair<int,int> > > p(n);
FORE(i,0,n){
stringstream out(contests[i]);
out>>p[i].first>>p[i].second.first>>p[i].second.second;
}
sort(all(p));
int dp[60];
int times[60];
memset(dp,0,sizeof(dp));
memset(times,0,sizeof(times));
FORE(i,0,n){
FORE(j,0,i+1){
if(p[i].first>=times[j] && dp[i+1]<dp[j]+p[i].second.second){
dp[i+1]=dp[j]+p[i].second.second;
times[i+1]=p[i].second.first;
}
}
}
int ret=0;
FORE(i,0,n+1)ret=max(ret,dp[i]);
return ret/100.0;
}
};
#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 ContestSchedule {
public:
double expectedWinnings(vector<string> contests) {
int n=contests.size();
vector<pair<int,pair<int,int> > > p(n);
FORE(i,0,n){
stringstream out(contests[i]);
out>>p[i].first>>p[i].second.first>>p[i].second.second;
}
sort(all(p));
int dp[60];
int times[60];
memset(dp,0,sizeof(dp));
memset(times,0,sizeof(times));
FORE(i,0,n){
FORE(j,0,i+1){
if(p[i].first>=times[j] && dp[i+1]<dp[j]+p[i].second.second){
dp[i+1]=dp[j]+p[i].second.second;
times[i+1]=p[i].second.first;
}
}
}
int ret=0;
FORE(i,0,n+1)ret=max(ret,dp[i]);
return ret/100.0;
}
};