UVa 11218 : KTV

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

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

問題概要：
9人で歌を歌いたい
3人１組でそれぞれが１回ずつ歌う
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;
}