AOJ 1264 Concert Hall Scheduling

追記 : タグが間違っていたのを修正

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1246

コンサートホールが2つあリ、{i} 日から {j} 日までの期間を料金 {w} で使用したいという申し込みが {n} 個来ている。期間が被らないように2つのコンサートホールにうまく割り振ったときの {w} の合計の最大値を求めよ。

解答

{ dp(i,j,k) := i } 個目までの申し込みで、ホールAは {j} 日目以降、ホールBは {k} 日目以降の予定を開けるように設定したときの合計の最大値
として更新していった。(漸化式はソースコードを見て。)予約の終了日の最大値を {d} として計算量は {O(n d^{2})} になる。

ちなみに最小費用流でも解ける。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());
    }
}