SDNUOJ 1033 采药

2024-02-01 16:08
文章标签 采药 1033 sdnuoj

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

                                                  1033.采药

Time Limit: 1000 MS    Memory Limit: 32768 KB
Total Submission(s): 573    Accepted Submission(s): 193

Description

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

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

Input

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

Output

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

Sample Input

100 5
77 92
22 22
29 87
50 46
99 90

Sample Output

133

Source

NOIP 2005 普及组

题意概括:在规定时间内采够价值最大的药。

解题思路:典型的0/1背包问题。

AC代码:

#include<stdio.h>
#include<algorithm>
using namespace std;int f[1005][1005], w[1005], c[1005];int main(void)
{int n, m, i, j;scanf("%d%d", &n, &m);for(i = 1; i <= m; i ++){scanf("%d%d", &w[i], &c[i]);}for(i = 1; i <= m; i ++){for(j = 1; j <= n; j ++){if(j >= w[i]){f[i][j] = max(f[i - 1][j - w[i]] + c[i], f[i - 1][j]);}else{f[i][j] = f[i - 1][j];}}}printf("%d\n", f[m][n]);return 0;
}
错误原因:无错,一次通过。

这篇关于SDNUOJ 1033 采药的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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]

采药问题 01背包

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

采药(信息学奥赛一本通-T1290)

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

疯狂的采药(洛谷-P1616)

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

采药(洛谷-P1048)

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

LightOJ 1033 - Generating Palindromes(dp)

题目链接:LightOJ 1033 - Generating Palindromes 代码 #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 105;int N, dp[maxn][maxn];char s[maxn], t[maxn];int solv

采药【(0-1)背包问题】

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

秋招突击——算法打卡——5/31——复习{采药问题、(状态压缩DP)小国王}——新做:{盛最多水的容器、整数转罗马数字}

文章目录 复习背包模型——采药问题状态压缩DP——小国王思路分析实现代码参考 新作盛最多的水个人实现思路分析实现代码 参考分析思路分析实现思路 整数转罗马数字个人实现思路分析实现代码 参考实现思路分析实现代码 总结 复习 背包模型——采药问题 原题链接这里回忆的时候,还是有点问题,就是起点值怎么写?并不确定!然后关于这个表达式,也是弄了半天才想起来,还是要多多练习一下

点头OJ 1033 . 骨牌覆盖 V2 ( 状态压缩 + 矩阵快速幂 )

题目链接~~> 做题感悟:先前做过一个类似的题,是俄罗斯的一道区域赛的题目,也是用的状态压缩 + 矩阵快速幂。 解题思路:状态压缩 + 矩阵快速幂                 构造一个矩阵 B [ i ] [ j ] 代表状态 i ,与状态 j 是否合法,j 代表上一行的状态,如果合法为 1 ,否则为 0 ,这样如果再得到初始各种状态的方案数的矩阵 A ,A 只有一列 ,这样 B *

蚯蚓的游戏问题 wikioi 1033

典型的网络流问题。把每一堆食物,分解成两个点(这里为什么要拆成两个点,我一直没想明白,后来才发现,题目中说每个结点只能经过一次,而假如每堆食物当成一个点,就无法保证改点只经过一次。要是不拆分,则此题只能拿50分),a,b。由a到b建立一个容量为1,cost为该堆食物量的负值的边(因为要求最大费用,所以用负值来代替,最后结果再取负即可)。在建立0结点和1结点。0结点向1结点建立一个容量为k,cost