首页 > [NOIP2005]采药
开通博客写题解
头像 savage
发表于 2019-08-21 17:40:27
题目描述 辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段 展开全文
去ta的博客 赞 (7) 回复(0) 收起
头像 cheeserish
发表于 2020-06-20 08:17:57
典型背包问题；感觉二维能过，who know ，一直没过；好吧，改成以为了； #include<bits/stdc++.h> using namespace std; #define int long long int t,m,tim[300],v[300],dp[1010]; sign 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 在刷题的单身狗很开心
发表于 2023-10-07 17:45:48
本题是一个01背包问题。其中时间其实就相当于背包问题里面的重量。 那么可以建立一个二维数组dp[i][j]表示对于第i个药草，时间为j来说它的最大价值。那么它的最大价值有选与不选两种情况，如果不选那么就是上一个药草，时间为j所对应的最大价值、如果选就是上一个药草对于j-a[i].tm的时间的最 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 默默然诶
发表于 2022-07-29 14:23:04
NC16693解题步骤基本一致 链接 #include "iostream" using namespace std; int V[101]; int W[101]; int dp[101][1001]; int main() { int T,n,i,x; cin>>T& 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 那万一赢了呢
发表于 2020-09-03 19:29:28
思路：动态规划的背包问题。建立二维数组dp[i][j]表示前i个物品不超过j时采到的草药的最大总价值。dp[i][j]=max(dp[i-1][j],dp[i-1][j-V[i]]+V[i]*W[i]) 特殊情况：当j<v[i]时，dp[i][j]=dp[i-1][j]。注意：可以不用初始化， 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”