• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            superman

            聚精會神搞建設 一心一意謀發展
            posts - 190, comments - 17, trackbacks - 0, articles - 0
               :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理

            Section 3.3 - Shopping Offers

            Posted on 2009-06-03 10:17 superman 閱讀(248) 評論(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 
            亚洲精品白浆高清久久久久久| 久久午夜无码鲁丝片秋霞| 国内精品久久久久影院日本| 久久久久久亚洲AV无码专区| 久久99国产精品久久99| 久久久久99精品成人片牛牛影视| 亚洲人成无码久久电影网站| 久久久久女人精品毛片| 久久久久人妻精品一区三寸蜜桃| 偷窥少妇久久久久久久久| 国产三级久久久精品麻豆三级| 青青青伊人色综合久久| 伊人久久综合精品无码AV专区| 国产精品久久成人影院| 久久中文字幕人妻熟av女| 中文字幕久久欲求不满| 久久无码高潮喷水| 成人国内精品久久久久影院VR| 亚州日韩精品专区久久久| 91精品国产91久久久久久| 久久国语露脸国产精品电影| 成人精品一区二区久久| 97精品久久天干天天天按摩| 久久精品极品盛宴观看| 国产精自产拍久久久久久蜜| 国产精品久久久亚洲| 亚洲国产另类久久久精品小说 | 国产精品视频久久| 伊人 久久 精品| 久久久久国产成人精品亚洲午夜| 午夜精品久久久久久久久| 亚洲欧美成人久久综合中文网| 久久99精品国产麻豆宅宅| 精品久久人妻av中文字幕| 亚洲香蕉网久久综合影视| 亚洲人成伊人成综合网久久久| 亚洲精品WWW久久久久久| 亚洲欧美另类日本久久国产真实乱对白| 国产成人精品久久一区二区三区av | 狠狠色狠狠色综合久久| 一日本道伊人久久综合影|