読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

UVa 11218 : KTV

UVa演習 2014/6/10 (火) 問5

問題リンク : http://uva.onlinejudge.org/external/112/11218.html

問題概要:
9人で歌を歌いたい
3人1組でそれぞれが1回ずつ歌う
3人の組み合わせとその組み合わせにすることで得られる得点が入力として与え等れるので得点を最大化せよ
同じ人が2回以上歌ってはいけない

解法:
ビットDP

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

int bit[90],s[90],dp[1<<9];

int main(){
  int n,CNT = 1;
  while( cin >> n , n ){
    printf("Case %d: ",CNT++);
    rep(i,n){
      int a,b,c;
      cin >> a >> b >> c >> s[i];
      --a,--b,--c;
      bit[i] = (1<<a) | (1<<b) | (1<<c);
    }

    rep(i,(1<<9)) dp[i] = -1;
    dp[0] = 0;
    rep(i,(1<<9)){
      if( dp[i] < 0 ) continue;
      rep(j,n){
        if( ( i | bit[j] ) != ( i ^ bit[j] ) ) continue;
        int bitmask = i | bit[j];
        dp[bitmask] = max(dp[bitmask],dp[i]+s[j]);
      }
    }
    printf("%d\n",dp[(1<<9)-1]);
  }
  return 0;
}