Posted on 2009-06-03 10:17
superman 阅读(221)
评论(0) 编辑 收藏 引用 所属分类:
USACO
1 #include <set>
2 #include <iostream>
3
4 using namespace std;
5
6 class SepcialOffer;
7 class Cart;
8
9 class SpecialOffer {
10 private:
11 int n;
12 int c[5]; //code of each product
13 int x[5]; //amount of each product needed
14 public:
15 int sp; //special price
16 public:
17 friend class Cart;
18 friend istream& operator>>(istream &is, SpecialOffer &t) {
19 is >> t.n;
20 for (int i = 0; i < t.n; i++)
21 is >> t.c[i] >> t.x[i];
22 is >> t.sp;
23 return is;
24 }
25 } so[100]; //special offers set
26
27 class Cart {
28 private:
29 int n;
30 int c[5]; //code of each product in the cart
31 int x[5]; //amount of each product int the cart
32 int p[5]; //the regular price of each product int the cart
33 public:
34 int bestp; //the best price of all products int the cart
35 public:
36 int regularPrice() {
37 int sum = 0;
38 for (int i = 0; i < n; i++)
39 sum += p[i] * x[i];
40 return sum;
41 }
42 bool couldUseSpecialOffer(const SpecialOffer &t) const {
43 for (int i = 0; i < t.n; i++) {
44 int j;
45 for (j = 0; j < n; j++)
46 if (t.c[i] == c[j] && t.x[i] <= x[j])
47 break;
48 if (j == n)
49 return false;
50 }
51 return true;
52 }
53 Cart useSpecialOffer(const SpecialOffer &t) const {
54 Cart nc = *this;
55 for (int i = 0; i < t.n; i++) {
56 int j;
57 for (j = 0; j < n; j++)
58 if (t.c[i] == c[j] && t.x[i] <= x[j]) {
59 nc.x[j] -= t.x[i];
60 break;
61 }
62 }
63 return nc;
64 }
65 bool operator<(const Cart &t) const {
66 for (int i = 0; i < n; i++)
67 if (x[i] != t.x[i])
68 return x[i] - t.x[i] < 0 ? true : false;
69 return false;
70 }
71 friend istream& operator>>(istream &is, Cart &t) {
72 is >> t.n;
73 for (int i = 0; i < t.n; i++)
74 is >> t.c[i] >> t.x[i] >> t.p[i];
75 return is;
76 }
77 } cart;
78
79 int so_num; //special offers num
80 set<Cart> cartSet;
81
82 int search(Cart cart)
83 {
84 set<Cart>::iterator it = cartSet.find(cart);
85 if (it != cartSet.end())
86 return it->bestp;
87
88
89 cart.bestp = INT_MAX;
90 for (int i = 0; i < so_num; i++)
91 if (cart.couldUseSpecialOffer(so[i]))
92 cart.bestp <?= (search(cart.useSpecialOffer(so[i])) + so[i].sp);
93
94 cart.bestp <?= cart.regularPrice();
95
96 cartSet.insert(cart);
97
98 return cart.bestp;
99 }
100
101 int main()
102 {
103 freopen("shopping.in", "r", stdin);
104 freopen("shopping.out", "w", stdout);
105
106 cin >> so_num;
107 for (int i = 0; i < so_num; i++)
108 cin >> so[i];
109 cin >> cart;
110
111 cout << search(cart) << endl;
112
113 return 0;
114 }
115