青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

posts - 12,  comments - 16,  trackbacks - 0
  
Shopping Offers
IOI'95

In a certain shop, each kind of product has an integer price. For example, the price of a flower is 2 zorkmids (z) and the price of a vase is 5z. In order to attract more customers, the shop introduces some special offers.

A special offer consists of one or more product items together for a reduced price, also an integer. Examples:

  • three flowers for 5z instead of 6z, or
  • two vases together with one flower for 10z instead of 12z.

Write a program that calculates the price a customer has to pay for a purchase, making optimal use of the special offers to make the price as low as possible. You are not allowed to add items, even if that would lower the price.

For the prices and offers given above, the (lowest) price for three flowers and two vases is 14z: two vases and one flower for the reduced price of 10z and two flowers for the regular price of 4z.

PROGRAM NAME: shopping

INPUT FORMAT

The input file has a set of offers followed by a purchase.
Line 1: s, the number of special offers, (0 <= s <= 99).
Line 2..s+1: Each line describes an offer using several integers. The first integer is n (1 <= n <= 5), the number of products that are offered. The subsequent n pairs of integers c and k indicate that k items (1 <= k <= 5) with product code c (1 <= c <= 999) are part of the offer. The last number p on the line stands for the reduced price (1 <= p <= 9999). The reduced price of an offer is less than the sum of the regular prices.
Line s+2: The first line contains the number b (0 <= b <= 5) of different kinds of products to be purchased.
Line s+3..s+b+2: Each of the subsequent b lines contains three values: c, k, and p. The value c is the (unique) product code (1 <= c <= 999). The value k indicates how many items of this product are to be purchased (1 <= k <= 5). The value p is the regular price per item (1 <= p <= 999). At most 5*5=25 items can be in the basket.

SAMPLE INPUT (file shopping.in)

2
1 7 3 5
2 7 1 8 2 10
2
7 3 2
8 2 5

OUTPUT FORMAT

A single line with one integer: the lowest possible price to be paid for the purchases.

SAMPLE OUTPUT (file shopping.out)

14

解答:
0 <= b <= 5,1 <= k <= 5,可用5*5*5*5*5的DP 每種買0~5個(gè),可以用6進(jìn)制表示,然后5維DP~OK!

狀態(tài)設(shè)置:F[a1][a2][a3][a4][a5]為買a1件物品1,a2件物品2,a3件物品3,a4件物品4,a5件物品5時(shí),所需的最少價(jià)格

邊界條件:F[0][0][0][0][0]=0;

狀態(tài)轉(zhuǎn)移方程:
F[a1][a2][a3][a4][a5]=min{F[ a1-P[i][1] ][ a2-P[i][2] ][ a3-P[i][3] ][ a4-P[i][4] ][ a5-P[i][5] ]+P[i][0]}
其中i=1..s+b; 且 ak-p[i][k]>=0

/*
ID: kuramaw1
PROG: shopping
LANG: C++
*/

#include 
<fstream>
#include 
<cstring>


using std::ifstream;
using std::ofstream;
using std::endl;

#define  MAX_T(a,b) ((a)>(b)?(a):(b))

#define  MAX 5
#define  MAX_S 100

int f[MAX+1][MAX+1][MAX+1][MAX+1][MAX+1];//min price

short s,b;
short s_p[MAX_S],component[MAX_S][MAX],p_num[MAX],p[MAX],p_t(0),order[MAX];

inline 
short product_code_to_order(short code)
{
    
for(int i=0;i<p_t;i++)
     
if(p_num[i]==code)
         
return i;
    p_num[p_t
++]=code;
    
return (p_t-1);

}

int main()
{
    ifstream 
in("shopping.in");
    
in>>s;
    memset(component,
0,sizeof(component));
    
for(int i=0;i<s;i++)
    {
        
short n;
        
in>>n;
        
for(int j=0;j<n;j++)
        {
            
short c,k;
            
in>>c>>k;
            component[i][product_code_to_order(c)]
=k;
        }
        
in>>s_p[i];
            
    }

    memset(order,
0,sizeof(order));
    memset(p,
0,sizeof(p));
    
in>>b;
    
for(int i=0;i<b;i++)
    {
        
short c,k,p1;
        
in>>c>>k>>p1;
        
short n=product_code_to_order(c);
        order[n]
=k;
        p[n]
=p1;
    }
    
in.close();

    
//do dp
    short ii[MAX];
#define loop(i)  for(ii[i]=0;ii[i]<=order[i];ii[i]++)
#define  F(a) f[a[0]][a[1]][a[2]][a[3]][a[4]]
    
    loop(
0) loop(1) loop(2) loop(3) loop(4)
    {

        F(ii)
=ii[0]*p[0]+ii[1]*p[1]+ii[2]*p[2]+ii[3]*p[3]+ii[4]*p[4];
        
for(short j=0;j<s;j++)
        {
            
short t[MAX];
            
for(short k=0;k<5;k++)
                t[k]
=MAX_T(0,ii[k]-component[j][k]);
            
if(F(t)+s_p[j]<F(ii))
                F(ii)
=F(t)+s_p[j];

        }
    }

    
//out
    ofstream out("shopping.out");
    
out<<F(order)<<endl;
    
out.close();


}


posted on 2009-08-13 11:46 kuramawzw 閱讀(522) 評論(0)  編輯 收藏 引用 所屬分類: USACO

只有注冊用戶登錄后才能發(fā)表評論。
網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


<2025年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

常用鏈接

留言簿(5)

隨筆分類

隨筆檔案

文章檔案

Algorithm

搜索

  •  

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲青色在线| 国产日韩精品视频一区| 亚洲福利久久| 欧美国产日韩xxxxx| 另类亚洲自拍| 亚洲精品在线三区| 亚洲免费观看高清在线观看| 国产精品红桃| 久久九九精品| 女女同性精品视频| 一区二区三区精密机械公司| 99这里只有精品| 国产性天天综合网| 亚洲国产二区| 欧美日韩一区二区三区免费| 欧美精品自拍| 亚洲免费人成在线视频观看| 欧美亚洲在线观看| 亚洲毛片在线看| 亚洲亚洲精品三区日韩精品在线视频| 久久久久久久久久久一区| 久久久成人精品| 在线亚洲欧美视频| 久久精品青青大伊人av| 日韩午夜黄色| 欧美一区二区三区日韩| 亚洲最新合集| 久久久国产精品一区二区中文| 亚洲免费av网站| 欧美一区二区在线播放| 日韩视频中文字幕| 久久精品国产综合| 亚洲主播在线播放| 久久三级视频| 欧美一区日本一区韩国一区| 欧美99久久| 久久久久久久高潮| 国产精品久久久爽爽爽麻豆色哟哟| 久久一区精品| 国产精品男gay被猛男狂揉视频| 欧美激情一区二区三区全黄| 国产视频自拍一区| 制服丝袜亚洲播放| 一本色道久久综合一区| 久久午夜电影网| 欧美在线视频一区二区三区| 欧美日韩精品一区二区在线播放 | 狠狠色综合日日| 亚洲伦理在线免费看| 在线观看不卡| 欧美一区二区| 欧美亚洲系列| 国产精品国产自产拍高清av| 亚洲人在线视频| 91久久精品国产91性色tv| 久久电影一区| 久久久久国产精品一区| 国产精品免费电影| 在线一区欧美| 亚洲午夜羞羞片| 欧美人与性动交a欧美精品| 欧美黄色免费| 亚洲欧洲日本一区二区三区| 欧美69wwwcom| 91久久精品www人人做人人爽| 亚洲国产经典视频| 免费在线看一区| 亚洲大胆视频| 亚洲精品永久免费| 欧美激情一区二区三区 | 亚洲在线视频观看| 国产精品v片在线观看不卡 | 久久这里有精品15一区二区三区| 国内成人精品视频| 久久久久久久久久久成人| 久久综合一区二区三区| 亚洲大片在线观看| 欧美韩国日本一区| 日韩一级在线| 欧美一区日本一区韩国一区| 国产在线欧美日韩| 麻豆成人av| 日韩午夜在线播放| 欧美一区国产一区| 1769国内精品视频在线播放| 欧美福利一区二区三区| 一区二区欧美日韩| 欧美一区二区精品| 亚洲缚视频在线观看| 欧美另类99xxxxx| 午夜精品成人在线| 欧美不卡一卡二卡免费版| 夜夜嗨av一区二区三区四季av| 欧美系列电影免费观看| 欧美一区二区视频在线| 欧美激情综合色| 午夜免费在线观看精品视频| 影音先锋中文字幕一区二区| 欧美精品成人一区二区在线观看 | 99精品国产热久久91蜜凸| 欧美一区二区三区免费视频| 在线观看欧美日韩| 欧美色网一区二区| 久久免费黄色| 亚洲先锋成人| 亚洲国产日韩一区| 欧美一区二区三区另类| 亚洲乱码国产乱码精品精98午夜| 国产精品网站在线观看| 亚洲影视九九影院在线观看| 国产综合在线看| 欧美日韩视频一区二区| 久久久人成影片一区二区三区 | 欧美在线视频播放| 99国产精品私拍| 激情文学一区| 国产精品视频免费一区| 欧美jizzhd精品欧美巨大免费| 先锋影音国产精品| 一区二区成人精品| 亚洲黄页一区| 欧美成人午夜免费视在线看片| 性欧美video另类hd性玩具| 亚洲美女视频| 亚洲国产91精品在线观看| 国产一区91| 国产欧美日韩精品一区| 欧美四级在线观看| 欧美国产一区在线| 久久视频在线免费观看| 久久成人国产精品| 亚洲欧美日韩一区二区三区在线观看 | 午夜精品av| 亚洲免费视频在线观看| 一本一本久久a久久精品牛牛影视| 在线欧美一区| 伊人成人网在线看| 精品二区久久| 在线精品一区| 精品69视频一区二区三区| 国产一二三精品| 国产日韩欧美另类| 国产一区二区成人| 国产综合在线看| 狠狠做深爱婷婷久久综合一区| 国产视频一区二区三区在线观看| 国产欧美日韩视频一区二区三区| 欧美二区在线播放| 欧美h视频在线| 欧美成年网站| 亚洲激情社区| 一区二区高清| 在线亚洲自拍| 欧美有码在线视频| 久久久久久久久久久一区| 欧美在线看片| 玖玖玖国产精品| 欧美激情一区二区三区在线视频观看| 欧美福利一区| 亚洲片区在线| 亚洲——在线| 久久精品在线免费观看| 老色鬼精品视频在线观看播放| 欧美成人高清| 国产精品久久久久久久浪潮网站| 国产精品美女久久福利网站| 国产日韩欧美精品综合| 在线观看久久av| 一区二区三区久久网| 欧美一级视频免费在线观看| 久久久久久久久久久久久9999| 欧美国产欧美亚洲国产日韩mv天天看完整 | 亚洲第一狼人社区| 99国产精品99久久久久久| 亚洲一区二区网站| 久久综合色婷婷| 最新国产乱人伦偷精品免费网站| 亚洲网站视频福利| 另类亚洲自拍| 国产精品国产三级国产普通话蜜臀| 国产欧美一区二区三区在线老狼 | 欧美国产亚洲另类动漫| 亚洲高清视频在线| 国产精品99久久久久久久女警| 久久精品国产成人| 欧美亚州一区二区三区 | 国产日产欧产精品推荐色| 亚洲高清免费视频| 先锋a资源在线看亚洲| 欧美激情精品久久久久久久变态 | 久久爱另类一区二区小说| 欧美激情国产日韩| 国内精品一区二区三区| 妖精视频成人观看www| 久久久久一本一区二区青青蜜月| 亚洲日本欧美天堂| 久久久久久久999精品视频| 欧美另类69精品久久久久9999| 激情综合色丁香一区二区| 亚洲一区二区欧美|