AOJ 2321 - Butterfly
- 問題
- 概要
n人の男とのデート予定がある。
デート予定は1時間区切りで6~22時の間で、複数の区間になることもある。
(例だとAdamは10~12,14~16でBobは12~13,18~20)
それぞれの男からは全てのデート予定をこなすと満足度Liを得られる。
得られる満足度の最大値を求めよ。
1<=n<=100
1<=Li<=100000000
- アイデア
ナップサック問題の重さがデート予定に変わった版。デート予定の競合などを調べるのにビットを利用した。そうするとデート予定の競合はAND演算、スケジュールの更新はOR演算により実現できるのでかなり綺麗に書ける。
- 実装(C++)
#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; } }