POJ 1170 - Shopping Offers

http://poj.org/problem?id=1170

概要

\(b\) 種類の商品があり，\(i\) 番目の商品は1つあたり \(p_i\) の値段である． 単体で買ったときよりも安くなるセットが \(s\) 種類存在する．

\(i\) 番目の商品をそれぞれ \(k_i\) 個買うのに必要な最小の金額を答える．

制約

• \(0 \le b \le 5\)
• \(1 \le p \le 999\)
• \(1 \le k \le 5\)
• \(0 \le s \le 99\)

解法

商品の組み合わせは \(6 ^ 5\) 通りしかないので，買う必要のある残りの商品をノード， セットをエッジとしたグラフ上でダイクストラすればよい．

 1 #include <cstdio>
 2 #include <queue>
 3 using namespace std;
 4 static const int K = 6;
 5 
 6 int encode(const int *v, int B)
 7 {
 8   int x = 0;
 9   for (int i = 0; i < B; i++) {
10     x = K*x + v[i];
11   }
12   return x;
13 }
14 
15 void decode(int *v, int B, int x)
16 {
17   for (int i = B-1; i >= 0; i--) {
18     v[i] = x % K;
19     x /= K;
20   }
21 }
22 
23 int main()
24 {
25   int B;
26   scanf("%d", &B);
27   int ks[5], ps[5];
28   static int m[1000];
29   for (int i = 0; i < B; i++) {
30     int c;
31     scanf("%d %d %d", &c, &ks[i], &ps[i]);
32     m[c] = i;
33   }
34 
35   int S;
36   scanf("%d", &S);
37   static int os[100][5];
38   int ops[100];
39   for (int i = 0; i < S; i++) {
40     int N;
41     scanf("%d", &N);
42     for (int j = 0; j < N; j++) {
43       int c, k;
44       scanf("%d %d", &c, &k);
45       os[i][m[c]] = k;
46     }
47     scanf("%d", &ops[i]);
48   }
49 
50   static const int INF = 10000000;
51   static int dist[7776];
52   fill_n(dist, 7776, INF);
53   priority_queue<pair<int, int> > q;
54   q.push(make_pair(0, encode(ks, B)));
55   dist[encode(ks, B)] = 0;
56   int ans = INF;
57   while (!q.empty()) {
58     const int c = -q.top().first;
59     const int ve = q.top().second;
60     q.pop();
61     int v[5];
62     decode(v, B, ve);
63 
64     if (c > dist[ve]) {
65       continue;
66     }
67 
68     int a = c;
69     for (int i = 0; i < B; i++) {
70       a += ps[i] * v[i];
71     }
72     ans = min(ans, a);
73 
74     for (int i = 0; i < S; i++) {
75       int w[5];
76       copy(v, v+B, w);
77       const int cc = c + ops[i];
78       int we;
79       for (int j = 0; j < B; j++) {
80         w[j] = v[j] - os[i][j];
81         if (w[j] < 0) {
82           goto SKIP;
83         }
84       }
85       we = encode(w, B);
86       if (cc < dist[we]) {
87         dist[we] = cc;
88         q.push(make_pair(-cc, we));
89       }
90 SKIP:
91       ;
92     }
93   }
94   printf("%d\n", ans);
95   return 0;
96 }