AOJ2321 Butterfly

Butterfly

Claire is a man-eater. She's a real man-eater. She's going around with dozens of guys. She's dating all the time. And one day she found some conflicts in her date schedule. D'oh! So she needs to pick some dates and give the others up. The dates are set by hours like 13:00 to 15:00.

デートのもっとも満足度の高くなるスケジュールを組む． ビットに当てて，デートの時間をビット集合と考える．

とする．時間 と の積集合が無い場合， 遷移可能()．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <bitset>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

ll dp[105][1 << 16];
ll L[105], S[105];

int main() {
  int n;
  while(cin >> n && n) {

      memset(L, 0, sizeof(L));
      memset(S, 0, sizeof(S));

      rep(i, n) {
          int m;
          cin >> m >> L[i];

          rep(j, m) {
              int s, t;
              cin >> s >> t;

              REP(k, s, t) {
                  S[i] |= 1 << (k-6);
              }
          }
      }

      memset(dp, 0, sizeof(dp));

      rep(i, n) {
          rep(j, 1<<16) {
              dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
          }

          rep(j, 1<<16) {
              if(j & S[i]) continue;
              dp[i+1][j | S[i]] = max(dp[i+1][j | S[i]], dp[i][j] + L[i]);
          }
      }

      ll ans = 0;
      rep(i, n + 1) {
          rep(j, 1<<16) {
              ans = max(ans, dp[i][j]);
          }
      }
      
      cout << ans << endl;
  }

  return 0;
}
Mar 22nd, 2016
250, aoj-icpc, 動的計画法