Solution 经典0-1背包问题, 题目的输入描述有点问题 第3-n+2行 -> 第 3 - m + 2 行 直接做背包是错的, 因为这里多了一个时间的限制, 价值随着时间而变化同样是背包但是先进背包和后进背包有区别因此需要考虑贪心策略下背包对于两个物体 , , 先取 物体比先取
展开全文
美味菜肴 (nowcoder.com)
被这题折磨了一天，呜呜呜
题意：给你n到菜，每道菜的美味度会随时间下降，告诉你下降速率，问在t时间内能够达到的最大的美味度是多少
思路：贪心+dp，我拿到就直接写01背包了，但是由于时间的因素导致每个时间下状态是会改变的，所以先进背包和后进背包是有区别的。比如
展开全文
讲道理,这题是真的lj.盗题就算了,题面还这么糟糕...贪心+dp不解释.https://ac.nowcoder.com/acm/problem/21314 具体看这题. #include <bits/stdc++.h>
using namespace std;
typedef long
展开全文
solution 贪心+dp。 做这个题我们需要处理两个问题。第一个是如何确定这些菜的顺序，第二个是确定了菜的顺序之后如何计算答案。 先来确定菜的顺序。仔细观察之后，发现其实这个问题贪心思路和“国王的游戏”一样。如果只考虑两种菜。我们如果让在前，那么选这两种菜的答案就是，否则就是。发现都有，所以我们
展开全文
NC14704 美味菜肴 题目地址： https://ac.nowcoder.com/acm/problem/14704 基本思路： 这题我们考虑01背包,但是由于选择的时间先后会影响结果,所以我们要根据谁先选择更优做一个贪心,我们先考虑两个菜肴i和j,如果先选择i再选择j那么结果为 如果
展开全文
这题是一个 01 背包的形式，唯一可能的解法是动态规划。 但在本题未经处理的情况下，动态规划是不能使用的。因为原图上的转移不是有向无环图，带来了后效性，使得动态规划出错。 于是我们需要安排一种转移顺序，使得原图的转移变成 DAG，从而应用动态规划解决问题。 结论是，一定存在一种最优方案 ，使得对于任
展开全文
一.闲谈 好吧，又是个套路题。。。 我对题面已无力吐槽。。。“第3-n+2行”明明应该是“第3-m+2行”，害我debug好久qwq 二.题解 首先，明显这是一个01背包问题（一开始看到食材无限时，以为是完全背包，结果被样例2卡了，样例出的不错。。。） 当然，我们直接打01背包是会错的，为什么？因为
展开全文
题意 件食材（每种食材的数量可以视为无限），小明连续工作 时间。每道菜肴的制作需要特定的一种食材以及一段时间，但是食材一旦放久就不新鲜了，菜的美味值会降低。第 道菜肴有三个属性 ，，， 是该菜肴的美味值， 是该菜肴所选食材不新鲜的速率，如果在第t时刻完成第i道菜则美味值为：，完成这道菜需要
展开全文
Solution 题面把意思说的比较清楚，其实可以比较明显的知道，这是一个从n件物品选一些出来，需要收益最大。挺明显的01背包，但是直接按照01背包来做确实错误的。想想为什么？没错，背包问题，是动态规划的过程，动态规划需要满足两个性质，最优子结构和无后效性。显然这个题目直接做不满足无后效性，改变做菜
展开全文
首先我们发现如果交换两个菜肴做的顺序，sum(ai)是不变的，也就是只剩下两个变量。此时容易想到可以通过代数运算得到做菜顺序。其实贪心思路也挺显然的，肯定是让减少的少的先做，并且同时和做这道菜的时间有关，所以我们此时通过代数运算得到当a.c/a.b < b.c/b.c的时候，先做a是优于先做b
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
