POJ-2047, AOJ-1246: Concert Hall Scheduling

keyword

問題概要

日程[i,j]( ⊆[1,365]), 金額wという予約がN(<1000)個以下与えられる。コンサートホールは同時に２つまで使用できる。得られる利益の最大値を求める問題。

解法

D=365とする。素朴に、dp[i日目][1つ目のホールが使い終わる日][2つ目のホールが使い終わる日]とすれば計算量O(D^3)位(本当はもう少し多いか?)で解ける。でも、2つのホールが埋まってる期間はどうせ他の予約を取ることはできないので、ホールの片方が開いている日に対してdp[i日目][使用中のホールの使い終わる日]とする。こうすると計算量O((D+N)^2)で解ける。実装時間25分。
O(D^3)の方の解法も、配列を使いまわしたりすればちゃんと通るかもしれない。

感想

Javaは多次元の動的配列を書くのが面倒なのでC++で書いた。STLのvectorくらい簡単に書く方法は無いものか。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector< pair<int,int> > sche[370];
int dp[370][370];

int solve(){
	for(int i=0; i<370; i++){
		for(int j=0; j<370; j++){
			dp[i][j] = -1;
		}
	}
	dp[1][1] = 0;
	for(int day=1; day<366; day++){
		for(int res=day; res<370; res++)if(dp[day][res]>=0){
			dp[day+1][max(day+1,res)] = max(dp[day+1][max(day+1,res)], dp[day][res]);

			if(day == res){
				for(int i=0; i<(int)sche[day].size(); i++){
					int end = sche[day][i].first;
					dp[day+1][end+1] = max(dp[day+1][end+1], dp[day][res] + sche[day][i].second);
				}
				for(int i=0; i<(int)sche[day].size(); i++){
					for(int j=i+1; j<(int)sche[day].size(); j++){
						int w = sche[day][i].second + sche[day][j].second;
						int d1 = min(sche[day][i].first, sche[day][j].first) + 1, d2 = max(sche[day][i].first, sche[day][j].first) + 1;
						dp[d1][d2] = max(dp[d1][d2], dp[day][res] + w);
					}
				}
			}
			else{
				for(int i=0; i<(int)sche[day].size(); i++){
					int end = sche[day][i].first, w = sche[day][i].second;
					if(res < end + 1){
						dp[res][end+1] = max(dp[res][end+1], dp[day][res] + w);
					}
					else{
						dp[end+1][res] = max(dp[end+1][res], dp[day][res] + w);
					}
				}
			}
		}
	}

	return *max_element(dp[366], dp[366]+370);
}

int main(){
	int N;
	while(scanf("%d",&N),N){
		for(int i=0; i<370; i++){
			sche[i].clear();
		}
		for(int i=0; i<N; i++){
			int st, en, we;
			scanf("%d%d%d",&st,&en,&we);
			sche[st].push_back(make_pair(en,we));
		}
		printf("%d\n",solve());
	}
	return 0;
}