AOJ0561 Books

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0561

割とすぐにDPだろうと思ったけど，どう遷移していいか分からない分からないとずっと悩んでいた．試しに値段，(ジャンルの個数，値段)の貪欲をしてWAを連発した

とした．5冊まで同じジャンルを売った時にプラスされる値段を見ると

となるので同じジャンルを売った時にプラスされる値段は，冊数をとすると，増えるのがされるのが個，増えるのが個あるのでとなる．
また冊選んだ時のコストは大きい順に取ればそれが最大となるので事前にソートしておくことでが求まる．
これが求まると，冊数を重さと見ると，冊を超えないナップサックになる．

青を遷移先とする．普通のナップサック?(蟻本p.52)はその品物を使わない遷移と使う遷移の2種類がある

今回の場合は，そのジャンルの本数文，遷移があるので下図のような状況になる．

この遷移のmaxを取ればが答えとなった．

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
70
71
72

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

#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 d[15][2005], dp[15][2005];

int main() {
  int n, K;
  cin >> n >> K;

  vector<int> id, v[2005];

  rep(i, n) {
      int a, b;
      cin >> a >> b;

      id.push_back(b-1);
      v[b-1].push_back(a);
  }

  sort(id.begin(), id.end());
  id.erase(unique(id.begin(),id.end()),id.end());

  rep(i, id.size()) {
      int j = id[i];
      sort(v[j].begin(), v[j].end(), greater<int>() );
  }

  memset(d, 0, sizeof(d));

  rep(i, id.size()) {
      int j = id[i];

      REP(k, 1, v[j].size()+1) {
          d[j][k] += d[j][k-1] + v[j][k-1] + (k-1) * 2;
      }
  }

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

  rep(i, id.size()) {
      rep(j, K + 1) {
          ll res = dp[i][j];
          rep(k, v[id[i]].size() + 1) {
              if(j >= k) {
                  res  = max(res, dp[i][j - k] + d[id[i]][k]);
              }
          }

          dp[i+1][j] = res;
      }
  }

  cout << dp[ id.size()][K] << endl;

  return 0;
}
Feb 12th, 2016
aoj, 動的計画法