| 比赛场次 | 391 |
|---|---|
| 比赛名称 | 叫图论的DP题 |
| 比赛状态 | 已结束比赛成绩 |
| 开始时间 | 2017-08-29 19:00:00 |
| 结束时间 | 2017-08-30 22:00:00 |
| 开放分组 | 全部用户 |
| 注释介绍 |
| 题目名称 | 魅力手镯 |
|---|---|
| 输入输出 | charm.in/out |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 16 MiB |
| 测试点数 | 10 简单对比 |
| 用户 | 结果 | 时间 | 内存 | 得分 |
|---|---|---|---|---|
 @@@ |
AAAAAAAAAA | 0.057 s | 0.38 MiB | 100 |
 Hyoi_0Koto |
AAAAAAAAAA | 0.085 s | 0.12 MiB | 100 |
 Hyoi_iostream |
AAAAAAAAAA | 0.103 s | 0.39 MiB | 100 |
 玉带林中挂 |
AAAAAAAAAA | 0.108 s | 0.43 MiB | 100 |
 kZime |
AAAAAAAAAA | 0.133 s | 0.34 MiB | 100 |
 FFF团 |
AAAAAAAAAA | 0.137 s | 0.40 MiB | 100 |
 bear |
AAAAAAAAAA | 0.139 s | 0.39 MiB | 100 |
 Regnig Etalsnart |
AAAAAAAAAA | 0.169 s | 0.19 MiB | 100 |
 Hyoi_ctime |
AAAAWWWWWW | 0.027 s | 4.94 MiB | 40 |
【题目描述】
贝茜去了大卖场的珠宝商店，发现一个魅力手镯，她想把最好的宝石镶嵌在这条手镯上。她有 N (1 ≤ N ≤ 3,402) 种可用宝石，每种宝石 i 都有其重量 Wi (1 ≤ Wi ≤ 400)，与价值 Di (1 ≤ Di ≤ 100)，每种宝石最多只能用一次。贝茜只能把总重量不超过 M (1 ≤ M ≤ 12,880)的宝石镶嵌到手镯上。
给你每个宝石的重量和价值，请你算出贝茜最多能把总价值为多大的宝石镶嵌到手镯上。
【输入格式】
第 1 行: 两个整数 N , M
第 2..N+1 行: 第 i+1 行 有两个整数， Wi 和 Di
【输出格式】
第 1 行: 一个整数，为镶嵌的宝石的总价值。
【输入样例】
4 6 1 4 2 6 3 12 2 7
【输出样例】
23
【来源】
译 by CmYkRgB123