AOJ 1246:Concert Hall Scheduling

問題リンク：Concert Hall Scheduling | Aizu Online Judge

問題概要：
自分はコンサートホールを２つ管理している
N人の人からそのコンサートホールのどちらか１つを借りたいというリクエストをうけており、
コンサートホールを借りたい期間（開始の日と終わりの日）と支払う金額があたえられる
自分はN人に対してそれぞれコンサートホールを貸すか断るかを選べる
うまくコンサートホールを貸し出した時に手にはいる最大の金額を求めよ
コンサートホールを貸した後、また貸し出し可能になるのはリクエストの終わりの日の次の日である

使用した言語：C＋＋

解法：

動的計画法
dp[i][j] := １つめの部屋がi日で2つめの部屋がj日のときの最大利益　とした
リクエストは開始時間が早い順にソートしておく

for i 0..N // リクエスト
for j 1..365 // 1つめの部屋の日
for k 1..365 // ２つめの部屋の日

といった感じのループになった　　　

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] := １つめの部屋が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;
}