UVa 11088 : End up with More Teams

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

問題リンク:http://uva.onlinejudge.org/external/110/11088.html

問題概要：
n人の人がいて、それぞれが３０以下のパワーをもっている
その中から3人チームを何組か作りたい
チーム全体のパワーは２０以上でなければならない
最大何チーム作れるだろうか

解法：
ビットDP
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 dp[1<<15][21];
int bc[1<<15],a[15];

int main(){
  rep(i,(1<<15)) bc[i] = __builtin_popcount(i);
  int n,CNT=1;
  while( cin >> n , n ){
    rep(i,(1<<n)) rep(j,21) dp[i][j] = -1;
    dp[0][0] = 0;
    printf("Case %d: ",CNT++);
    rep(i,n) scanf("%d",a+i);
    sort(a,a+n);
    int maxi = 0;
    rep(bitmask,(1<<n)){
      bool phase = ((bc[bitmask]%3)==2);
      rep(i,21){
        if( dp[bitmask][i] < 0 ) continue;
        rep(j,n){
          if( (bitmask>>j) & 1 ) continue;
          int cost = i + a[j];
          if( phase ) {
            if( cost < 20 ) continue;
            dp[bitmask|(1<<j)][0] = max(dp[bitmask|(1<<j)][0],dp[bitmask][i]+1);
            maxi = max(maxi,dp[bitmask|(1<<j)][0]);
          } else {
            cost = min(cost,20);
            dp[bitmask|(1<<j)][cost] = max(dp[bitmask|(1<<j)][cost],dp[bitmask][i]);
          }
        }
      }
    }
    printf("%d\n",maxi);
  }
  return 0;
}