首页 > 其他分享 >【洛谷 P1048】[NOIP2005 普及组] 采药 题解(动态规划+01背包)

【洛谷 P1048】[NOIP2005 普及组] 采药 题解(动态规划+01背包)

时间:2024-09-17 12:51:01浏览次数:14  
标签:NOIP2005 01 采到 int 题解 tt mm 草药 dp

[NOIP2005 普及组] 采药

题目描述

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

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

输入格式

第一行有 【洛谷 P1048】[NOIP2005 普及组] 采药 题解(动态规划+01背包)_数据 个整数 【洛谷 P1048】[NOIP2005 普及组] 采药 题解(动态规划+01背包)_数据_02【洛谷 P1048】[NOIP2005 普及组] 采药 题解(动态规划+01背包)_ci_03)和 【洛谷 P1048】[NOIP2005 普及组] 采药 题解(动态规划+01背包)_数据_04【洛谷 P1048】[NOIP2005 普及组] 采药 题解(动态规划+01背包)_数据_05),用一个空格隔开,【洛谷 P1048】[NOIP2005 普及组] 采药 题解(动态规划+01背包)_数据_02 代表总共能够用来采药的时间,【洛谷 P1048】[NOIP2005 普及组] 采药 题解(动态规划+01背包)_数据_04 代表山洞里的草药的数目。

接下来的 【洛谷 P1048】[NOIP2005 普及组] 采药 题解(动态规划+01背包)_数据_04 行每行包括两个在 【洛谷 P1048】[NOIP2005 普及组] 采药 题解(动态规划+01背包)_#include_09【洛谷 P1048】[NOIP2005 普及组] 采药 题解(动态规划+01背包)_数据_10 之间(包括 【洛谷 P1048】[NOIP2005 普及组] 采药 题解(动态规划+01背包)_#include_09【洛谷 P1048】[NOIP2005 普及组] 采药 题解(动态规划+01背包)_数据_10)的整数,分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

样例 #1

样例输入 #1

70 3
71 100
69 1
1 2

样例输出 #1

3

提示

【数据范围】

  • 对于 【洛谷 P1048】[NOIP2005 普及组] 采药 题解(动态规划+01背包)_#include_13 的数据,【洛谷 P1048】[NOIP2005 普及组] 采药 题解(动态规划+01背包)_ci_14
  • 对于全部的数据,【洛谷 P1048】[NOIP2005 普及组] 采药 题解(动态规划+01背包)_数据_15

【题目来源】

NOIP 2005 普及组第三题


思路

使用一个一维数组 dp 存储每个时间能够采到的最大价值。

状态转移方程:

dp[j] = max(dp[j], dp[j - tt] + mm);

在初始化 dp 数组时,dp[0] 赋值为 0。

在每次状态转移时,遍历所有时间,对于当前时间 j,判断是否可以采摘当前草药,如果可以,就将当前价值加上上一个时间能够采到的最大价值,更新 dp[j]。最后,输出 dp[t] 即可。


AC代码

#include <iostream>
#include <algorithm>
#define AUTHOR "HEX9CF"
using namespace std;

const int N = 1e4 + 5;

int t, m;
int tt, mm;
int dp[N];

int main()
{
    dp[0] = 0;
    cin >> t >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> tt >> mm;
        for (int j = t; j >= tt; j--)
        {
            dp[j] = max(dp[j], dp[j - tt] + mm);
        }
    }
    cout << dp[t] << endl;
    return 0;
}

标签:NOIP2005,01,采到,int,题解,tt,mm,草药,dp
From: https://blog.51cto.com/HEX9CF/12036671

相关文章

  • 201909-2 小明种苹果(续)ccfcsp
    一道简单的模拟。。。includeincludeusingnamespacestd;intmain(){constintN=1010;booldrop[N]={false};intn,m,i,j,cnt=0,cnt1=0;cin>>n;inty;intsum=0,sum1,temp=0;intindex;for(i=0;i<n;i++){ sum1=0;scanf("%d",&m);for(j=0;j&......
  • win2012服务器使用 Certbot 生成 Let's Encrypt 的域名证书
    1、安装windows版本的certbot,目前最新版是Certbot2.9.02、命令行输入[email protected]:\website\xxx\-dwww.xxx.cn其中,[email protected]为电子邮箱地址,d:\website\xxx\为网站根目录,www.xxx.cn为域名3、后面会有两次输入,第一......
  • 历年CSP-J初赛真题解析 | 2019年CSP-J初赛阅读程序(16-33)
    学习C++从娃娃抓起!记录下CSP-J备考学习过程中的题目,记录每一个瞬间。附上汇总贴:历年CSP-J初赛真题解析|汇总_热爱编程的通信人的博客-CSDN博客#include<cstdio>#include<cstring>usingnamespacestd;charst[100];intmain(){scanf("%s",st);intn......
  • 【架构设计】多级缓存:应用案例与问题解决策略
    【架构设计】多级缓存:应用案例与问题解决策略多级缓存系统的工作原理及其在提升应用性能方面的关键作用。通过对比本地缓存与分布式缓存的特点| 原创作者/编辑:凯哥Java                    | 分类:架构设计系列教程多级缓存系统:提升性能的......
  • 洛谷P1016
    题目传送门:传送门p1016题目描述一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市之间的距离 D1D1​、汽车油箱的容量 CC(以升为单位)、每升汽油能行驶的距离 D2D2​、出发点每升汽油价格PP和沿途油站数 NN(NN 可以为零),油站 ii......
  • day01 GO环境搭建
    day01环境搭建Go和C语言、C++、Python、Java等一样都是编程语言。学习任何一门编程语言本质上都分3步走:第一步:安装解释器或编译器。第二步:学相关编程语言语法,然后写代码。第三步:用已安装解释器或编译器去运行自己写的代码,这样代码就会去完成我们编写的功能了。Go......
  • 【架构设计】多级缓存:应用案例与问题解决策略
      【架构设计】多级缓存:应用案例与问题解决策略 多级缓存系统的工作原理及其在提升应用性能方面的关键作用。通过对比本地缓存与分布式缓存的特点 | 原创作者/编辑:凯哥Java                    | 分类:架构设计系列教程 ......
  • 【PAT_Python解】1014 福尔摩斯的约会
    原题链接:PTA|程序设计类实验辅助教学平台Tips:以下Python代码仅个人理解,非最优算法,仅供参考!ls=[]#装输入数据,你也可以S1,S2,S3,S4=input(),···D,H,M='','',''dict={'A':'MON','B':'TUE','C':'WED','D�......
  • NOIP 2017 普及组初赛试题及解析(第三部分:阅读程序(3-4))
    ......
  • PMP--一模--解题--101-110
    文章目录11.风险管理--过程--识别风险→实施定性风险分析→实施定量风险分析→规划风险应对→实施风险应对→监督风险101、[单选]在项目即将进入收尾阶段时,项目经理发现了一项原来没有考虑到的新风险。该风险一旦发生,可能给最终的可交付成果带来重要影响,甚至可能使其不......