| 题目名称 | 1649. [SPOJ 699] 巨大的背包 |
|---|---|
| 输入输出 | hugeknapsack.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2014-05-29加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：5， 提交：21， 通过率：23.81% | ||||
 水中音 |
100 | 0.000 s | 0.00 MiB | C++ |
 张灵犀不和我一般见识真可怕呢（笑 |
100 | 0.017 s | 0.33 MiB | C++ |
|
mikumikumi |
100 | 0.018 s | 0.33 MiB | C++ |
 digital-T |
100 | 0.023 s | 0.33 MiB | C++ |
 cstdio |
100 | 0.044 s | 0.34 MiB | C++ |
|
水中音 |
20 | 0.000 s | 0.00 MiB | C++ |
|
digital-T |
20 | 0.019 s | 0.33 MiB | C++ |
 bigger |
0 | 0.001 s | 0.26 MiB | C |
|
digital-T |
0 | 0.002 s | 0.32 MiB | C++ |
|
张灵犀不和我一般见识真可怕呢（笑 |
0 | 0.012 s | 0.33 MiB | C++ |
| 关于 巨大的背包 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
再次跪在读入上。。。
千万不要用%lld读入int类型的变量 | ||||
|
啥来着…部分贪心，明白大体思想，limit的值实在难想
| ||||
|
http://hi.baidu.com/zsasuke/item/a49ee68cad3ddb844514cf7b这个题解里的程序过不了……不知道为什么……
懒得仔细去查了……做人呢，最重要的就是开心……实在不行就拿我程序对拍吧…… | ||||
【题目描述】
我们的国王赢得了一场血腥的战争，因此现在整片大陆都是我们的了。这片大陆的特殊之处在于这里有许多美丽的纯金雕像。国王希望往他的宫殿里带回尽可能多的黄金。我们已经发现了那里有N种雕像，并且——不可思议的——每种雕像都有无数个。每一座第i种雕像的重量为W[i]个单位，并且占据V[i]个单位的体积。国王希望最大化他带回宫殿的金子总数。我们可以我们可以使用S个袋子来完成这一目标，每个的容量都是Y。所有的袋子都独立地装入纯金雕像，不能把雕像切开。不过，可以把两个袋子缝在一起，需要消耗C个单位的黄金。把三个袋子缝在一起需要消耗2*C，因为这需要两次缝合，以此类推。你的任务是找出国王最多可以获得多少金子，也就是说，带回去金子的总重量减去缝合袋子的花费。
【输入格式】
输入包含多组数据。
输入文件的第一行有一个整数T，即数据组数。
接下来是T组数据。
每组数据格式如下：
第一行：N S Y C
接下来有N行，每行含两个整数W[i]和V[i]。
【输出格式】
输出一个整数，即最多能获得多少金子。
【样例输入】
2
2 5 3 1
1 2
5 7
2 5 3 1
1 2
7 5
【样例输出】
6
17
【提示】
1<=S<=1000
1<=Y<=1000000000
1<=N<=1000
1<=W[i]<=100
1<=V[i]<=18
输出不超过64位带符号整数范围。
1<=T<=20
所有的W[i]和V[i]是素数或1.
【来源】
ByteCode 2006