[BZOJ] 1625: [Usaco2007 Dec]宝石手镯-程序员宅基地

1625: [Usaco2007 Dec]宝石手镯

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 1347  Solved: 952
[Submit][Status][Discuss]

Description

贝茜在珠宝店闲逛时,买到了一个中意的手镯。很自然地,她想从她收集的 N(1 <= N <= 3,402)块宝石中选出最好的那些镶在手镯上。对于第i块宝石,它的重量为W_i(1 <= W_i <= 400),并且贝茜知道它在镶上手镯后能为自己增加的魅力值D_i(1 <= D_i <= 100)。由于贝茜只能忍受重量不超过M(1 <= M <= 12,880)的手镯,她可能无法把所有喜欢的宝石都镶上。 于是贝茜找到了你,告诉了你她所有宝石的属性以及她能忍受的重量,希望你能帮她计算一下,按照最合理的方案镶嵌宝石的话,她的魅力值最多能增加多少。

Input

* 第1行: 2个用空格隔开的整数:N 和 M

* 第2..N+1行: 第i+1行为2个用空格隔开的整数:W_i、D_i,分别为第i块宝石 的重量与能为贝茜增加的魅力值

Output

* 第1行: 输出1个整数,表示按照镶嵌要求,贝茜最多能增加的魅力值

Sample Input

4 6
1 4
2 6
3 12
2 7

输入说明:

贝茜收集了4块宝石,她能忍受重量最大为6的手镯。


Sample Output

23

输出说明:

贝茜把除了第二块宝石的其余所有宝石都镶上手镯,这样她能增加
4+12+7=23的魅力值,并且所有宝石的重量为1+2+3 <= 6,同样符合要求。

HINT

 

Source

 

Analysis

背包裸题

 

Code

 1 #include<cstdio>
 2 #define maxn 1000000
 3 #include<iostream>
 4 using namespace std;
 5 
 6 int n,m,a,b,DP[maxn];
 7 
 8 int main(){
 9     scanf("%d%d",&n,&m);
10     
11     for(int i = 1;i <= n;i++){
12         scanf("%d%d",&a,&b);
13         for(int j = m;j >= a;j--){
14             DP[j] = max(DP[j],DP[j-a]+b);
15         }
16     }
17     
18     printf("%d",DP[m]);
19     
20     return 0;
21 }
显得我做题很多似的= =

转载于:https://www.cnblogs.com/Chorolop/p/7460562.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30344995/article/details/95922271

智能推荐

python difflib 编辑距离_Python Edit_Distance包_程序模块 - PyPI - Python中文网-程序员宅基地

文章浏览阅读413次。编辑距离用于计算序列之间编辑距离和对齐的python模块。我需要一种方法来计算python中序列之间的编辑距离。我没有能够找到任何合适的库来实现这一点,所以我自己编写了一个。在那里似乎有许多可用于计算编辑的编辑距离库两个字符串之间的距离,但不是两个序列之间的距离。这完全是用python编写的。这种实现可能是在python中优化为更快。如果在C中实现。库API是根据difflib.sequencem..._edit distance python lib

antd upload组件 手动上传-程序员宅基地

文章浏览阅读3.8k次,点赞2次,收藏15次。antd 的upload组件是点开对话框后,按下确实就会上传,而且如果多选文件也会反复调用后端接口来完成上传。因为项目需要,所以要实现手动上传,和一次性上传多个文件(调用一次后端接口)在实现这个功能时,我翻阅了很多博客,可能是因为版本原因,很多代码都无用,最后还是通过翻阅官方文档,才最终实现。..._antd upload

sqlite3 环境搭建_sqlite 部署-程序员宅基地

文章浏览阅读246次。注意 第一步在一个文件下打开终端然后 sqlite3 student.db(创建一个数据库),然后再create stu。callback 回调函数 (只有sql为查询语句的时候,才会执行此语句)6--删除一列(sqlite3 不支持) 用下面方法。功能 :打开sqlite 数据库。功能 :关闭sqlite 数据库。基本sql命令,不以 . 夹头,db:指向sqlite句柄的指针。将新表的名字改为原来表的名字。sqlite3的基本命令。功能:执行一条sql语句。以 . 开头的命令。_sqlite 部署

canal-adapter趟坑实践:canal-server的kafka SASLPLAIN方式鉴权适配_canal adapter kafka sasl-程序员宅基地

文章浏览阅读1.4w次。前言canal-server同步到kafka本身是支持Kerberos方式的鉴权的,但是鉴于项目现在使用的kafka集群使用的是SASL/PLAIN的鉴权方式,所以需要对canal-server同步kafka做一下适配改造。准备kafka SASL/PLAIN鉴权的搭建我参考的这篇文章kafka SASL/PLAIN鉴权的搭建了解如何使用java向以SASL/PLAIN方式鉴权的kafk..._canal adapter kafka sasl

Android adb shell相关命令_android的shell命令工具:设备规范管理-程序员宅基地

文章浏览阅读711次。adb(调试桥):debug工具。adb作用:借助adb工具,可以管理设备或手机模拟器状态。adb相关操作命令如下: 1. 显示系统中全部Android平台: android list targets2. 显示系统中全部AVD(模拟器): android list avd3. 创建AVD(模拟器): android create avd_android的shell命令工具:设备规范管理

Centos 7.9 在线安装 VirtualBox 7.0_centos安装virtualbox-程序员宅基地

文章浏览阅读769次,点赞10次,收藏7次。Centos 7.9 在线安装 VirtualBox 7.0_centos安装virtualbox

随便推点

Autodesk官方卸载工具软件安装教程-程序员宅基地

文章浏览阅读1.4w次,点赞9次,收藏10次。Autodesk卸载工具是一个专门用于Autodesk软件的卸载工具,可以自动识别电脑中的所有Autodesk软件,只需一键点击就能将Autodesk的软件完美卸载,并且不保留任何痕迹,这款卸载工具就可以帮助用户全面卸载Autodesk软件。_autodesk官方卸载工具

JDBC报错:Cannot find class: com.mysql.jdbc.Driver-程序员宅基地

文章浏览阅读4.9k次。1.配置书写错误:配置文件value值引号内不能有空格,属性文件配置信息末尾不能有空格(1)打开属性文件中com.mysql.jdbc.Driver后发现多了一个空格(如下我标出了),所以写属性文件时一定别多输入多余的空格了。 jdbc.driverClassName=com.mysql.jdbc.Driver(此处有空格)(2)配置文件中的value值的" "号中前面或..._cannot find class: com.mysql.jdbc.driver

软件常用术语_软件术语-程序员宅基地

文章浏览阅读1.8k次。软件常用术语,免得你面对各种设计模式头发晕_软件术语

Machine Learning 2 - 非线性回归算法分析_非线性回归分析方法-程序员宅基地

文章浏览阅读2.8k次。2017-08-02@erixhao 技术极客TechBoosterAI 机器学习第二篇 - 非线形回归分析。我们上文深入本质了解了机器学习基础线性回归算法后,本文继续研究非线性回归。非线性回归在机器学习中并非热点,并且较为小众,且其应用范畴也不如其他广。鉴于此,我们本文也将较为简单的介绍,并不会深入展开。非线性回归之后,我们会继续经典机器学习算法包括决策_非线性回归分析方法

hive基本函数_josn mincol-程序员宅基地

文章浏览阅读164次。一、关系运算:1.等值比较: =语法:A=B操作类型:所有基本类型描述:如果表达式A与表达式B相等,则为TRUE;否则为FALSE举例:hive>select 1 from lxw_dual where 1=1;12.不等值比较: <>语法: A <> B操作类型:所有基本类型描述:如果表达式A为NULL,或者表..._josn mincol

FI 与SD MM相关接口配置_sd 和fi 接口产生什么凭证?-程序员宅基地

文章浏览阅读767次。1 FI/SD 借口配置FI/SD通过tcode VKOA为billing设置过帐科目,用户可以创建自己的科目定义数据表。 科目是做到COA级的,通过KOFI/KOFK这两个condition type确定分别过帐到FI和CO凭证中。 由于PricingProc.是同Sale_sd 和fi 接口产生什么凭证?

推荐文章

热门文章

相关标签