山东省质量建设监督总站网站,竞价点击软件工具,北京企业网页制作,网站建设及服务合同题目背景
此题为纪念 LiYuxiang 而生。
题目描述
LiYuxiang 是个天资聪颖的孩子#xff0c;他的梦想是成为世界上最伟大的医师。为此#xff0c;他想拜附近最有威望的医师为师。医师为了判断他的资质#xff0c;给他出了一个难题。医师把他带到一个到处都是草药的山洞里对…题目背景
此题为纪念 LiYuxiang 而生。
题目描述
LiYuxiang 是个天资聪颖的孩子他的梦想是成为世界上最伟大的医师。为此他想拜附近最有威望的医师为师。医师为了判断他的资质给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说“孩子这个山洞里有一些不同种类的草药采每一种都需要一些时间每一种也有它自身的价值。我会给你一段时间在这段时间里你可以采到一些草药。如果你是一个聪明的孩子你应该可以让采到的草药的总价值最大。”
如果你是 LiYuxiang你能完成这个任务吗
此题和原题的不同点
1. 每种草药可以无限制地疯狂采摘。
2. 药的种类眼花缭乱采药时间好长好长啊师傅等得菊花都谢了
输入格式
输入第一行有两个整数分别代表总共能够用来采药的时间 t 和代表山洞里的草药的数目 m。
第 2 到第 (m1) 行每行两个整数第 (i1) 行的整数 ai,bi 分别表示采摘第 i 种草药的时间和该草药的价值。
输出格式
输出一行这一行只包含一个整数表示在规定的时间内可以采到的草药的最大总价值。
输入输出样例
输入 #1
70 3 71 100 69 1 1 2
输出 #1
140
说明/提示
数据规模与约定 对于 30 %的数据保证 m≤103 。 对于 100%的数据保证 1≤m≤1041≤t≤107且 1≤ai,bi≤104。
解题思路
本题和采药类似只是把01背包改成了完全背包
其实并不难01背包是从 t 到 wi 进行 dp而完全背包恰恰相反是从 wi 到 t 进行 dp
动态方程二维 dpi,jmax(dpi−1,j,dpi−1,j−wivi)
可以发现方程的结果与第一维无关可以将方程简化到 dpimax(dpi−wivi,dpi)
当然滚动数组也是一个很好的解法
还有一个重要的地方注意开 long long题目一开始数据规模不严谨导致错误题解可以通过导致被 yummy hack 十年 OI 一场空不开 long long 见祖宗 就是强调了 long long 的必要性
AC
#includebits/stdc.h
using namespace std;
#define int long long
int w[100005],c[100005];
int dp[10000005];
signed main(){int v,n;cinvn;for(int i1;in;i){cinw[i]c[i]; } for(int i1;in;i){for(int tw[i];tv;t){dp[t]max(dp[t],dp[t-w[i]]c[i]); } }coutdp[v];return 0;
}结尾
希望大家多多关注
如果你能支持一下我我十分感谢
如果有人想在洛谷上做题可以点下方链接
https://www.luogu.com.cn/
如果你喜欢或想了解一下其他的算法可以看看以下这些
洛谷指南
洛谷使用指南_洛谷怎么看-CSDN博客
题目详解系列部分
【万题详解】DFS搜索专题合集中-CSDN博客
【万题详解】DFS搜索专题合集上-CSDN博客
【万题详解】P1314 [NOIP2011 提高组] 聪明的质监员-CSDN博客
【万题详解】洛谷P1282 多米诺骨牌-CSDN博客
【万题详解】洛谷P1238 走迷宫-CSDN博客
【万题详解】洛谷P1135奇怪的电梯-CSDN博客
【万题详解】洛谷P1510 精卫填海-CSDN博客
【万题详解】洛谷P1252 马拉松接力赛-CSDN博客
【万题详解】洛谷P1359 租用游艇-CSDN博客
【百题详解】洛谷P8508 做不完的作业-CSDN博客
【万题详解1】洛谷P1230 智力大冲浪-CSDN博客
【全网首发】洛谷贪心题解合集2-CSDN博客
【全网首发】洛谷贪心题解集合-CSDN博客
洛谷二分题集3题-CSDN博客
游戏系列
C棋类小游戏2-CSDN博客
C自创棋类小游戏-CSDN博客
C史上最坑小游戏-CSDN博客 C自创小游戏-CSDN博客
C下雪-CSDN博客
C讲解系列算法
C第十五讲高精度算法-CSDN博客
C第十四讲动态规划初步-CSDN博客
C第十三讲BFS广度优先搜索-CSDN博客
C:第十二讲DFS深搜二_c匿名函数dfs-CSDN博客 C第十一讲DFS深搜-CSDN博客
C第十讲二分查找-CSDN博客
前缀和与差分
C第九讲前缀和与差分-CSDN博客
贪心
C第八讲贪心算法1-CSDN博客
C讲解系列基础入门
排序
C第七讲冒泡排序-CSDN博客
函数
C第6讲max和min函数_c min函数-CSDN博客
C第五讲函数初步-CSDN博客
for循环数组
C第四讲for循环及数组-CSDN博客
if语句else语句及运算
C第三讲C中的逻辑运算符及if else语句-CSDN博客
基础
C第二讲输入与输出-CSDN博客
C第一讲认识C编译器-CSDN博客
欢迎收看希望大家能三连
最后认识一下我是爱编程的喷火龙廖我们有缘再见
