华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1159|回复: 0
打印 上一主题 下一主题

P2792 [JSOI2008]小店购物

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
跳转到指定楼层
楼主
发表于 2018-9-26 17:13:06 | 只看该作者 回帖奖励 |正序浏览 |阅读模式
https://www.luogu.org/problemnew/show/P2792

题目背景
JSOI集训队的队员发现,在他们经常活动的集训地,有一个小店因为其丰富的经营优惠方案深受附近居民的青睐,生意红火。

题目描述
小店的优惠方案十分简单有趣:

一次消费过程中,如您在本店购买了精制油的话,您购买香皂时就可以享受2.00元/块的优惠价;如果您在本店购买了香皂的话,您购买可乐时就可以享受1.50元/听的优惠价......诸如此类的优惠方案可概括为:如果您在本店购买了商品A的话,您就可以以P元/件的优惠价格购买商品B(购买的数量不限)。

有趣的是,你需要购买同样一些商品,由于不同的买卖顺序,老板可能会叫你付不同数量的钱。比如你需要一块香皂(原价2.50元)、一瓶精制油(原价10.00元)、一听可乐(原价1.80元),如果你按照可乐、精制油、香皂这样的顺序购买的话,老板会问你要13.80元;而如果你按照精制油、香皂、可乐这样的顺序购买的话,您只需付13.50元。

该处居民发现JSOI集训队的队员均擅长电脑程序设计,于是他们请集训队的队员编写一个程序:在告诉你该小店商品的原价,所有优惠方案及所需的商品后,计算至少需要花多少钱(不允许购买任何不必要的商品,即使这样做可能使花的钱更少)。

输入输出格式
输入格式:
输入文件第一行为一个整数n(1<=n<=50),表示小店的商品总数。

接下来是n行,其中第(i+1)行由一个实数ci(0<ci<=1000)和一个整数mi(0<=mi<=100)组成,其间由一个空格分隔,分别表示第i种商品的原价和所需数量。第(n+2)行又是一个整数k,表示小店的优惠方案总数。

接着k行,每行有二个整数A,B(1<=A,B<=n)和一个实数P(0<=P<1000),表示一种优惠方案,即如果您购买了商品A,您就可以以P元/件的优惠价格购买商品B,P小于商品B的原价。所有优惠方案的(A,B)都是不同的。为了方便老板不收分币,所以所有价格都不出现单位分。

输出格式:
输出只有一个实数,表示最少需要花多少钱。输出实数须保留两位小数。

输入输出样例
输入样例#1:
4
10.00 1
1.80 1
3.00 0
2.50 2
2
1 4 2.00
4 2 1.50
输出样例#1:
15.50

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 02:58 , Processed in 0.188460 second(s), 24 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表