AOJ 2321 - Butterfly

問題概要

Claireという女性がいる。彼女がN人の男性のうちの何人かとデートをするプランを立てることを考える。N人の男性にはそれぞれM個のデートをする時間帯(SからE)とその男性とデートしたときの満足度Lが与えられる。彼女は各男性に対して、全ての時間帯でデートができるのであればその男性とデートし満足度が得られる。この満足度を最大化せよ。時間帯が重なるとデートはできない。

制約

• 1 ≤ N ≤ 100
• 1 ≤ M ≤ 16
• 1 ≤ L ≤ 100000000
• 6 ≤ S < E ≤ 22

解法

時間が6から22であり16区間なのでそれをbitで考えてbitDPする。
dp[i][j] := i人目までで時間帯のビットjを使用したときの最大の満足度

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX 110
typedef long long ll;
 
int N,M;
ll dp[MAX][1<<16],L[MAX];
int bit[MAX];
 
ll solve(int n,int S){
  if(n == N){ return 0LL; }
  if(dp[n][S] != -1){
    return dp[n][S];
  }
  ll res = 0LL;
  res = max(res,solve(n+1,S));
  bool ok = true;
  for(int i = 0 ; i < 16 ; i++){
    if((S >> i) & (bit[n] >> i)){
      ok = false;
      break;
    }
  }
  if(ok){
    res = max(res,solve(n+1,S|bit[n])+L[n]);
  }
  return dp[n][S] = res;
}
 
int main(){
  int S,E;
  while(cin >> N, N){
    memset(dp,-1,sizeof(dp));
    for(int i = 0 ; i < N ; i++){
      cin >> M >> L[i]; bit[i] = 0;
      for(int j = 0 ; j < M ; j++){
        cin >> S >> E;
        S -= 6; E -= 6;
        for(int k = S ; k < E ; k++){
          bit[i] |= (1<<k);
        }
      }
    }
    cout << solve(0,0) << endl;
  }
  return 0;
}