AOJ 1264 Concert Hall Scheduling
追記 : タグが間違っていたのを修正
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1246
コンサートホールが2つあリ、 日から 日までの期間を料金 で使用したいという申し込みが 個来ている。期間が被らないように2つのコンサートホールにうまく割り振ったときの の合計の最大値を求めよ。
解答
個目までの申し込みで、ホールAは 日目以降、ホールBは 日目以降の予定を開けるように設定したときの合計の最大値
として更新していった。(漸化式はソースコードを見て。)予約の終了日の最大値を として計算量は になる。
ちなみに最小費用流でも解ける。AOJ の Public Solutions で人の答えを見て気づいたが、そっちの方は単純明快すぎてびっくりした。
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; #define loop(i,a,b) for(int i=(a); i<int(b);i++) #define rep(i,b) loop(i,0,b) struct triple { int l,r,w; }; triple a[1000]; int dp[2][400][400]; // i,j 以降は空いている int n; int solve(){ memset(dp,0,sizeof(dp)); sort(a,a + n,[](triple const& a,triple const& b){ return a.l < b.l; }); rep(i,n){ auto next=dp[i&1]; auto cur=dp[i+1&1]; int l=a[i].l,r=a[i].r,w=a[i].w; rep(j,380)rep(k,380){ next[j][k]=cur[j][k]; if(j) next[j][k]=max(next[j][k],next[j-1][k]); if(k) next[j][k]=max(next[j][k],next[j][k-1]); if(j==r) next[j][k]=max(next[j][k],cur[l][k]+w); if(k==r) next[j][k]=max(next[j][k],cur[j][l]+w); } } return max(dp[0][370][370],dp[1][370][370]); } int main(){ while (scanf("%d",&n),n){ rep(i,n){ int l,r,w; scanf("%d%d%d",&l,&r,&w); r++; a[i]={l,r,w}; } printf("%d\n",solve()); } }