AOJ1246 Concert Hall Scheduling

問題リンク Concert Hall Scheduling

• 概要

コンサートホールが2つある。N個の利用申請があり、各申請の内容は、ホールを1つ期間[i, j]の間だけ費用wで借りたいというものである。ホールを[i, j]の間貸し出している期間中、他の利用者はそのホールを一切利用することができない。ホールを貸し出して得られる利益の最大値を答えよ。
1 <= N <= 1000
1 <= i <= j <= 365
1 <= w <= 10^6

• 解法

DPです。
dp[i][j][k]: i番目の申請までを考えて、ホール1を[1, j]、ホール2を[1, k]の間だけ貸し出して得られる最大利益
という表を埋めて解きました。
申請は借りる期間の終端の昇順でソートしておきます。
計算量は1000*365^2で1億を超えますが何とかなります。
もっと速く工夫できるような気がしてならないのですが思い付きそうで思い付かないです。

• ソース

import java.util.Arrays;
import java.util.Scanner;

//Concert Hall Scheduling
public class AOJ1246 {

	class R implements Comparable<R>{
		int s, t, c;
		public R(int s, int t, int c) {
			this.s = s;
			this.t = t;
			this.c = c;
		}
		public int compareTo(R o) {
			return t-o.t;
		}
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		int[][][] dp = new int[2][366][366];
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			R[] r = new R[n];
			for(int i=0;i<n;i++)r[i]=new R(sc.nextInt(), sc.nextInt(), sc.nextInt());
			Arrays.sort(r);
			int x = 0;
			for(int i=0;i<2;i++)for(int j=0;j<366;j++)for(int k=0;k<366;k++)dp[i][j][k]=0;
			for(int i=0;i<n;i++,x=1-x)for(int j=1;j<366;j++)for(int k=1;k<366;k++){
				int max = Math.max(dp[1-x][j][k], Math.max(dp[x][j-1][k], dp[x][j][k-1]));
				if(r[i].t==j)max = Math.max(max, dp[1-x][r[i].s-1][k]+r[i].c);
				if(r[i].t==k)max = Math.max(max, dp[1-x][j][r[i].s-1]+r[i].c);
				dp[x][j][k] = max;
			}
			System.out.println(dp[1-x][365][365]);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1246().run();
	}
}