AOJ 1246:Concert Hall Scheduling
問題リンク:Concert Hall Scheduling | Aizu Online Judge
問題概要:
自分はコンサートホールを2つ管理している
N人の人からそのコンサートホールのどちらか1つを借りたいというリクエストをうけており、
コンサートホールを借りたい期間(開始の日と終わりの日)と支払う金額があたえられる
自分はN人に対してそれぞれコンサートホールを貸すか断るかを選べる
うまくコンサートホールを貸し出した時に手にはいる最大の金額を求めよ
コンサートホールを貸した後、また貸し出し可能になるのはリクエストの終わりの日の次の日である
使用した言語:C++
解法:
動的計画法
dp[i][j] := 1つめの部屋がi日で2つめの部屋がj日のときの最大利益 とした
リクエストは開始時間が早い順にソートしておく
for i 0..N // リクエスト
for j 1..365 // 1つめの部屋の日
for k 1..365 // 2つめの部屋の日
といった感じのループになった
dp配列の更新は今見ている日にちがリクエストの終わりの日+1であるならば
(リクエストの開始の日の最大利益)+(リクエストを受けることではいる利益) と今はいっている最大利益を比較して行った
コード:
#include<iostream> #include<vector> #include<algorithm> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) using namespace std; typedef vector<int> VI; typedef vector<VI> VVI; struct P { int s,e,cost; P(int s=0,int e=0,int cost=0):s(s),e(e),cost(cost){} bool operator < (const P& p)const { if(s!=p.s)return s < p.s; return e < p.e; } }; int main() { int N; while(cin >> N,N) { int MAX = 367; //dp[i][j] := 1つめの部屋がi日めで2つ目の部屋がj日の時の最大利益 VVI dp(MAX,VI(MAX,0)); vector<P> requests(N); rep(i,N) cin >> requests[i].s >> requests[i].e >> requests[i].cost; sort(requests.begin(),requests.end()); rep(k,N) { VVI DP = dp; REP(i,1,MAX) { REP(j,1,MAX) { if(i == j && j == requests[k].e+1) { DP[i][j] = max(DP[i][j], max(dp[requests[k].s][j]+requests[k].cost, dp[i][requests[k].s]+requests[k].cost)); } else if(j == requests[k].e+1) { DP[i][j] = max(DP[i][j], dp[i][requests[k].s]+requests[k].cost); } else if(i == requests[k].e+1) { DP[i][j] = max(DP[i][j], dp[requests[k].s][j]+requests[k].cost); } DP[i][j] = max(DP[i][j], max(DP[i-1][j],DP[i][j-1])); } } dp = DP; } cout << dp[MAX-1][MAX-1] << endl; } return 0; }