问题 A: 【动态规划】采药_二维数组_一维数组
2024-10-18 23:24:54
问题 A: 【动态规划】采药
时间限制: 1 Sec 内存限制: 64 MB
提交: 35 解决: 15
[提交][状态][讨论版]
题目描述
山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值,在一段时间内如何让采到的草药价值最大。
输入
第一行有两个用空格隔开的整数T和M(1≤T,M≤100),T代表总共采药时间,M代表草药数目。接下来的M行每行包括两个在1到100之间(包括1和100)的整数,分别表示采摘某种草药的时间和这株草药的价值。
输出
只包含一个整数,表示在规定的时间内可以采到的草药的最大总价值。
样例输入
70 3
71 100
69 1
1 2
样例输出
3 解题思路:实际就是01背包,用二维数组的时候注意:需要考虑j<t[i]的情况,因为后面会有用到dp[i-1][j-t[i]] (j<t[i])的情况。
所以还是学着用一维数组做01背包吧,既节省空间有不用考虑这么多情况。
代码:二维数组:
#include<cstdio>
#include <iostream>
#include <cstring> using namespace std; int dp[][]; int main(){
int T;
int M;
int maxx=; int t[];
int p[];
while(scanf("%d %d",&T,&M)!=EOF){
maxx=;
memset(dp,,sizeof(dp));
for(int i=;i<=M;i++){
scanf("%d %d",&t[i],&p[i]);
}
for(int i=;i<=M;i++){
for(int j=;j<=T;j++){
if(j>=t[i]){
dp[i][j]=max(dp[i-][j],dp[i-][j-t[i]]+p[i]);
}else{
dp[i][j]=dp[i-][j];
}
}
}
printf("%d\n",dp[M][T]);
}
return ;
}
一维数组:
#include <iostream>
#include <cstdio>
#include <cstring> using namespace std; int a[]={};
int t[]={};
int p[]={}; void zeroonepack(int T,int t,int p){
for(int i=T;i>=t;i--){
a[i]=max(a[i],a[i-t]+p);
}
} int main()
{
int T,M;
while(scanf("%d %d",&T,&M)!=EOF){
memset(a,,sizeof(a));
for(int i=;i<M;i++){
scanf("%d %d",&t[i],&p[i]);
}
for(int i=;i<M;i++){
zeroonepack(T,t[i],p[i]);
}
printf("%d\n",a[T]);
}
return ;
}
最新文章
- Oracle数据库的创建以及远程连接(PL/SQL Developer远程连接数据库)
- [Head First设计模式]餐馆中的设计模式——命令模式
- 如何向新手程序员介绍Java编程
- Spring Framework------>;version4.3.5.RELAESE----->;Reference Documentation学习心得----->;Spring Framework中的spring web MVC模块
- Linux Shell编程二
- [NOIP2009] 普及组
- iOS FMDB官方使用文档 G-C-D的使用 提高性能(翻译)(转)
- Careercup - Microsoft面试题 - 6282862240202752
- JavaScript高级程序设计(第三版)第三章 基本概念
- Firefox插件一键切换兼容IE
- C++语言十进制数,CDecimal(未完成)
- Bozo排序
- css布局详解(二)——标准流布局(Nomal flow)
- [置顶] ssize_t与size_t-linux
- gem install bundler
- 给上传文件的input控件";美容";
- 使用JSON JavaScriptSerializer 进行序列化或反序列化时出错。字符串的长度超过了为 maxJsonLength属性
- [Postman]代理(16)
- tab 切换实现方法
- [BZOJ3011][Usaco2012 Dec]Running Away From the Barn
热门文章
- HighCharts日期及数值格式化
- 点击每个li输出里面的内容(前端很常问的面试题之一)
- SQL如何将A,B,C替换为&#39;A&#39;,&#39;B&#39;,&#39;C&#39;
- web开发前端学习
- ML_R kNN
- Apache服务器httpd.exe进程占用cpu超过50%的解决方法
- Ubuntu 14 安装 “宋体,微软雅黑,WPS Office的symbol、wingdings、wingdings 2、wingdings 3、webding字体,Consolas雅黑混合版编程字体” 等 Windows 7 下的字体
- Hibernate之映射一对一关联
- mytbatis小问题
- OS X 添加环境变量