裏紙

ほぼ競プロ、たまに日記

AOJ 2321 - Butterfly

  • 問題

Butterfly | Aizu Online Judge

  • 概要

n人の男とのデート予定がある。
デート予定は1時間区切りで6~22時の間で、複数の区間になることもある。
(例だとAdamは10~12,14~16でBobは12~13,18~20)
それぞれの男からは全てのデート予定をこなすと満足度Liを得られる。
得られる満足度の最大値を求めよ。

1<=n<=100
1<=Li<=100000000

ナップサック問題の重さがデート予定に変わった版。デート予定の競合などを調べるのにビットを利用した。そうするとデート予定の競合はAND演算、スケジュールの更新はOR演算により実現できるのでかなり綺麗に書ける。

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

typedef struct{
  int m; //スケジュールをビットで持つ
  long L;
}guy;

int n;
guy g[100];

long dp[101][65537]; //2^16+1
//今x人目に注目していて、yのスケジュール状態での満足度の最大値
long rec(int x, int y){
  if(dp[x][y]>=0) return dp[x][y];

  if(x==n) return 0;

  long ret=0;

  //x人目のスケジュール状態と今の状態yを比較
  if((g[x].m & y)==0){
    //両方のビットが同時に立つビットがない
    //x人目とデートするかしないかの選択権がある
    ret = max( rec(x+1,y), rec(x+1,y|g[x].m)+g[x].L );
  }
  else ret = rec(x+1,y);

  return dp[x][y] = ret;
}

int main(){
  while (1) {
    //input
    cin >> n;
    if(n==0) break;
    for(int i=0; i<n; ++i){
      int p;
      cin >> p >> g[i].L;
      g[i].m=0;
      for(int j=0; j<p; ++j){
        int s,e;
        cin >> s >> e;
        for(int k=s; k<e; ++k) g[i].m += (1<<(k-6));
      }
    }

    //solve
    memset(dp, -1, sizeof(dp));
    cout << rec(0,0) << endl;
  }
}