疯狂的采药(洛谷-P1616)

2024-06-17 22:32
文章标签 洛谷 疯狂 采药 p1616

本文主要是介绍疯狂的采药(洛谷-P1616),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

LiYuxiang是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同种类的草药,采每一种都需要一些时间,每一种也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”

如果你是LiYuxiang,你能完成这个任务吗?

此题和原题的不同点:

1.每种草药可以无限制地疯狂采摘。

2.药的种类眼花缭乱,采药时间好长好长啊!师傅等得菊花都谢了!

输入输出格式

输入格式:

输入第一行有两个整数T(1 <= T <= 100000)和M(1 <= M <= 10000),用一个空格隔开,T代表总共能够用来采药的时间,M代表山洞里的草药的数目。接下来的M行每行包括两个在1到10000之间(包括1和10000)的整数,分别表示采摘某种草药的时间和这种草药的价值。

输出格式:

输出一行,这一行只包含一个整数,表示在规定的时间内,可以采到的草药的最大总价值。

输入输出样例

输入样例#1:

70 3
71 100
69 1
1 2

输出样例#1:

140

思路:完全背包入门题,套模板即可

源代码

#include<iostream>
using namespace std;
int cmp(int x,int y)
{if(x>y)	return x;else return y;
}
int main()
{int time,num;int signle_time[10000],price[10000],dp[100000]={0};int max=0;int i,j;cin>>time>>num;//时间与种类for(i=1;i<=num;i++)	cin>>signle_time[i]>>price[i];//每种药的采摘时间与价值for(i=1;i<=num;i++)//比较每种药材{for(j=signle_time[i];j<=time;j++)//从当前药材时间开始,到最大时间为止{dp[j]=cmp(dp[j],dp[j-signle_time[i]]+price[i]);if(dp[j]>max)	max=dp[j];//寻找最大值}}cout<<max<<endl;return 0;
}

 

这篇关于疯狂的采药(洛谷-P1616)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1070622

相关文章

高精度计算(代码加解析,洛谷p1601,p1303)除法待更新

目录 高精度加法 高精度减法 高精度乘法 高精度加法 我们知道在c++语言中任何数据类型都有一定的表示范围。当两个被加数很大时,正常加法不能得到精确解。在小学,我们做加法都采用竖式方法。那么我们也只需要按照加法进位的方式就能得到最终解。 8 5 6+ 2 5 5-------1 1 1 1 加法进位: c[i] = a[i] + b[i];if(c[i] >=

洛谷 凸多边形划分

T282062 凸多边形的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 先整一个半成品,高精度过两天复习一下补上 #include <iostream>#include <algorithm>#include <set>#include <cstring>#include <string>#include <vector>#include <map>

能量项链,洛谷

解释:  环形dp问题还是考虑将环拉直,可以参考我上一篇文章:环形石子合并 [2 3 5 10 2] 3 5 10 将环拉直,[]内是一个有效的区间,可以模拟吸收珠子的过程,         如[2 3 5] <=>(2,3)(3,5)    2是头,3是中间,5是尾 len >= 3:因为最后[2 10 2]是最小的可以合并的有效区间 len <= n + 1因为[2 3

洛谷P5490扫描线

0是最小的数字,将一个线段看成一个区间,对于一个矩形,从下扫到上,入边为1,而出边为-1,意思是将这个区间上的所有点加1(区间修改).把线段表示为Line[i],其中记录了l,r,h,tag,左右端点,高度,入边还是出边(1或-1) 那么每次区间修改后不为0的区间它的值可能是1,2,3或者是其它数字,这不好统计,可以将它转化一下,0是不是表示没有被覆盖过的地方,我们只要统计0的个数然后用总长减去

YoloV10改进策略:下采样改进|自研下采样模块(独家改进)|疯狂涨点|附结构图

文章目录 摘要自研下采样模块及其变种第一种改进方法 YoloV10官方测试结果改进方法测试结果总结 摘要 本文介绍我自研的下采样模块。本次改进的下采样模块是一种通用的改进方法,你可以用分类任务的主干网络中,也可以用在分割和超分的任务中。已经有粉丝用来改进ConvNext模型,取得了非常好的效果,配合一些其他的改进,发一篇CVPR、ECCV之类的顶会完全没有问题。 本次我将这个模

挤牛奶洛谷uasco

题目描述 三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶。第一个农民在300秒(从5点开始计时)给他的牛挤奶,一直到1000秒。第二个农民在700秒开始,在 1200秒结束。第三个农民在1500秒开始2100秒结束。期间最长的至少有一个农民在挤奶的连续时间为900秒(从300秒到1200秒),而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300秒(从1200秒到1500秒)。

当电商“邂逅”微信支付 比想象还疯狂

微信支付在为移动电商带来高效解决方案的同时,也促进了新的移动电商生态的形成。” 12月6日,在腾讯“当电商‘邂逅’移动支付”把脉沙龙上,微信团队与电商代表、外部专家就 微信支付与电商的现状和前景展开研讨,指出当前的“微信价”现象代表了电商企业对微信支付商业模式的探索。未来,微信支付有望发展成为移动互联网时代的一项基础能力,其与微信平台的紧密结合,将帮助电商企业构建起移动互联网时代的全新商业生态。

P1616 疯狂的采药(完全背包模板)

//这是一道完全背包的题,并且需要用一维数组优化空间,否则会MLE #include <bits/stdc++.h>using namespace std;//t表示可以用来采药的时间(相当于背包容量)//m表示草药的数目(相当于物品数量)int t, m; //m<=10^4,t<=10^7 //w[i]表示采摘第i种草药需要花费的时间(相当于背包模型中物品的体积) //v[i]

洛谷刷题(7)

P8738 [蓝桥杯 2020 国 C] 天干地支 题目描述 古代中国使用天干地支来记录当前的年份。 天干一共有十个,分别为:甲(jiǎ)、乙(yǐ)、丙(bǐng)、丁(dīng)、戊 (wù)、己(jǐ)、庚(gēng)、辛(xīn)、壬(rén)、癸(guǐ)。 地支一共有十二个,分别为:子(zǐ)、丑(chǒu)、寅(yín)、卯(mǎo)、辰(chén)、巳(sì)、午(wǔ)、

C++ 洛谷 哈希表(对应题库:哈希,hash)习题集及代码

马上就开学了,又一个卷季,不写点东西怎么行呢?辣么,我不准备写那些dalao们都懂得,熟练的,想来想去,最终还是写哈希表吧!提供讲解&题目&代码解析哦! 奉上题目链接: 洛谷题目 - 哈希,hash 1、哈希、哈希表(hash)简介 哈希(Hash)是一种将任意长度的输入映射为固定长度输出的算法。哈希函数的输出值称为哈希值或散列值。哈希函数具有以下特性: 确定性:对于相同的输入