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

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>
            欧美一区日韩一区| 欧美精品入口| 亚洲免费观看高清完整版在线观看| 免费看精品久久片| 欧美精品三级日韩久久| 亚洲在线一区二区| 欧美福利电影网| 久久精品国产亚洲精品 | 亚洲欧美精品伊人久久| 亚洲成人在线免费| 麻豆9191精品国产| 模特精品在线| 久久久久久久精| 国产精品日本| 一区二区三区欧美视频| 在线看国产一区| 先锋资源久久| 亚洲少妇中出一区| 欧美aaaaaaaa牛牛影院| 久久精品国产成人| 日韩午夜av| 欧美日韩在线观看一区二区| 欧美a级片网站| 最近中文字幕mv在线一区二区三区四区 | 亚洲一区bb| 性欧美在线看片a免费观看| 国产精品老牛| 久久国产精品久久久| 日韩午夜在线| 伊人成年综合电影网| 美日韩精品视频免费看| 含羞草久久爱69一区| 久久久久久一区二区| 欧美成年人网| 99热免费精品在线观看| 国产精品chinese| 欧美一级二区| 亚洲激情欧美| 欧美日韩国产综合久久| 亚洲精品激情| 久久成人资源| 亚洲国产三级在线| 国产精品海角社区在线观看| 在线一区二区三区四区五区| 久久久久久精| 亚洲理伦在线| 一区二区视频欧美| 国产精品美女久久久免费| 久久av在线看| 亚洲欧美日韩国产一区二区三区| 欧美专区在线观看| 在线视频你懂得一区二区三区| 国产一区二区三区直播精品电影| 另类激情亚洲| 午夜日韩视频| 午夜精彩视频在线观看不卡| 欧美精品久久久久久久久久| 久久激情婷婷| 免费成人网www| 欧美日韩三级电影在线| 国产精品高清在线观看| 国产精品美女久久久久aⅴ国产馆| 欧美午夜激情小视频| 国产欧美va欧美不卡在线| 国产女主播一区二区| 亚洲激情第一区| 国产一区99| 国产一二精品视频| 国产日韩一区二区| 欧美精品一区在线观看| 欧美精品一线| 欧美性久久久| 国产欧美丝祙| 亚洲欧洲综合另类在线| 亚洲香蕉伊综合在人在线视看| 亚洲欧美在线高清| 久久综合色一综合色88| 亚洲国产免费看| 亚洲肉体裸体xxxx137| 一本色道久久综合| 久久人人爽人人爽| 国产精品美女久久久| 亚洲国产精品毛片| 久久精品国产成人| 亚洲精选一区二区| 欧美大片专区| 亚洲国产精品电影在线观看| 亚洲一级影院| 亚洲国产精品视频| 久久精品国产亚洲5555| 欧美色区777第一页| 亚洲精品乱码久久久久久日本蜜臀 | 中文精品99久久国产香蕉| 久久全球大尺度高清视频| 一区二区三区蜜桃网| 欧美电影在线播放| 亚洲韩日在线| 老司机成人在线视频| 欧美一区亚洲二区| 国产亚洲va综合人人澡精品| 欧美一级视频精品观看| 亚洲尤物视频在线| 国产亚洲一区在线| 午夜精品久久久| 午夜精品短视频| 国产一区二区三区久久 | 日韩视频精品| 欧美激情成人在线视频| 免费在线成人av| 日韩一级不卡| 亚洲一区在线视频| 好看的日韩av电影| 亚洲电影第三页| 国产精品国产三级国产普通话蜜臀| 亚洲丝袜av一区| 欧美制服第一页| 日韩亚洲在线| 欧美一区视频| 亚洲精品自在在线观看| 99亚洲伊人久久精品影院红桃| 国产精品欧美经典| 欧美激情国产日韩精品一区18| 欧美精品一区二| 久久久亚洲影院你懂的| 欧美激情第10页| 美女免费视频一区| 欧美无乱码久久久免费午夜一区 | 久久久久久久一区| 亚洲欧美综合国产精品一区| 久久综合网络一区二区| 久久成人综合视频| 国产精品亚洲第一区在线暖暖韩国| 欧美成人综合一区| 好看的日韩视频| 久久99伊人| 久久久久在线| 国户精品久久久久久久久久久不卡| 日韩视频在线观看一区二区| 亚洲成色最大综合在线| 久久精品一本| 欧美搞黄网站| 一本久道久久久| 欧美日韩免费在线视频| 亚洲美女黄色| 午夜视频在线观看一区二区三区| 欧美日韩在线高清| 亚洲一区在线看| 久久在线免费视频| 亚洲日本精品国产第一区| 欧美1区免费| 亚洲一区欧美激情| 久久天天躁夜夜躁狠狠躁2022| 国外成人性视频| 欧美精品97| 久久在线免费观看视频| 91久久极品少妇xxxxⅹ软件| 夜夜嗨av一区二区三区| 国产精品一二一区| 欧美一区网站| 99精品国产在热久久| 久久久国产精彩视频美女艺术照福利 | 欧美天天在线| 久久中文欧美| 亚洲午夜电影在线观看| 美女日韩欧美| 午夜精品www| 中文日韩欧美| 一本色道久久加勒比精品| 黄网站色欧美视频| 国产精品亚洲精品| 国产精品久久久久久久7电影| 欧美精品高清视频| 免费在线看成人av| 麻豆精品视频| 欧美大香线蕉线伊人久久国产精品| 亚洲欧美日韩电影| 欧美中文在线观看国产| 性欧美在线看片a免费观看| 99视频精品| 在线中文字幕日韩| 亚洲免费观看| 亚洲一区欧美| 久久久久亚洲综合| 久久久久一区二区三区四区| 久久久蜜臀国产一区二区| 欧美一区综合| 欧美激情日韩| 国产精品久久久久婷婷| 国产女主播一区二区| 伊人夜夜躁av伊人久久| 亚洲高清视频中文字幕| 夜夜嗨av一区二区三区中文字幕| 亚洲精品久久久久| 亚洲欧美日韩电影| 麻豆亚洲精品| 亚洲小说春色综合另类电影| 久久精品国产一区二区电影| 欧美—级a级欧美特级ar全黄| 欧美午夜精品久久久久免费视| 国产精品人人做人人爽|