AOJ 2285 - Anipero

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2285

解法

シークレットアーティストの選び方は全通り試す．

すると残りの資金 L で満足度を最大化するようにスタンダードアーティストを選べばよく，これはナップザック DP で解ける． このとき，選んだ人数も同時に記録していき X 以上のときだけを採用するようにする．

計算量が怪しいが 1:77 で通った．

最初にスタンダードアーティストを雇用金に関してソートしてその順で更新していくのを忘れて一回 WA してた．

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int L, N, M, X;
 8   while (cin >> L >> N >> M >> X && L != 0) {
 9     static pair<int,int> sec[100];
10     for (int i = 0; i < N; i++) {
11       string s;
12       cin >> s >> sec[i].first >> sec[i].second;
13     }
14     static pair<int,int> sta[100];
15     for (int i = 0; i < M; i++) {
16       string s;
17       cin >> s >> sta[i].first >> sta[i].second;
18     }
19     sort(sta, sta+M);
20 
21     int ans = 0;
22     for (int i = 0; i < N; i++) {
23       for (int j = i; j < N; j++) {
24         int E = L - sec[i].first;
25         int S = sec[i].second;
26         if (i != j) {
27           E -= sec[j].first;
28           S += sec[j].second;
29         }
30         if (E < X) {
31           continue;
32         }
33         static int dp[1000];
34         static int cnt[1000];
35         fill_n(dp, E+1, 0);
36         fill_n(cnt, E+1, 0);
37         int a = 0;
38         for (int k = 0; k < M; k++) {
39           for (int l = E - sta[k].first; l >= 0; l--) {
40             if (dp[l+sta[k].first] < dp[l]+sta[k].second) {
41               dp[l+sta[k].first] = dp[l]+sta[k].second;
42               cnt[l+sta[k].first] = cnt[l]+1;
43               if (cnt[l+sta[k].first] >= X) {
44                 a = max(a, dp[l+sta[k].first]);
45               }
46             }
47           }
48         }
49         if (a != 0) {
50           ans = max(ans, a+S);
51         }
52       }
53     }
54     cout << ans << endl;
55   }
56   return 0;
57 }