网站页面
当前课程
成员
常规
第一章 分治算法
第二章 递归算法
第三章 排列组合问题
第四章 高精度算法
第五章 排序算法
第六章 穷举算法
第七章 贪心算法
第八章 递推算法
第九章 搜索算法
第十章 模拟算法
收购魔法石
成绩 | 100 | 开启时间 | 2016年05月30日 星期一 18:55 |
折扣 | 0.8 | 折扣时间 | 2016年05月30日 星期一 18:55 |
允许迟交 | 是 | 关闭时间 | 2016年05月30日 星期一 18:55 |
输入文件 | pearls.in | 输出文件 | pearls.out |
【题目描述】收购魔法石(pearls.cpp/c/pas)ZJU 1563
由于魔法石的巨大消耗,魔法学院需要购买不同等级的魔法石,有高等级也有低等级,每个等级有一定的价钱。每一次买一种等级的魔法石,必须多买10个。 为了节约用钱,魔法学院会采取如下的方法:比如,需要买5颗1等级(低)的魔法石,每颗10 元,100颗2等级(高)的魔法石,每颗20元。如果每个等级都买到需要:(5+10)×10+(100+10)×20=2350 元。但如果不买低等级的魔法石而换买高等级的,则用钱为(5+100+10)×20=2300元,这样就省钱了!
要求输出买所有的魔法石(可以把低等级的换买高等级的,但不能把高等级的换买低等级的)需要花费的最少钱数。
【输入格式】
第一行包含一个数字N,即有N组测试数据。每组测试数据的行数由c (1 ≤ c ≤ 100)来决定,c行中的每一行都包含两个数字ai 和 pi,第一个数字表示需要的魔法石数 (1≤ai ≤1000),第二个数字表示该类魔法石的价值(1≤ pi ≤ 1000)。魔法石的品质由低至高严格按顺序给出。所有数字均为整数。
【输出格式】
每组测试数据输出一行,每行均为最少钱数。
【输入样例】
2
100 1
100 2
【输出样例】
330