链接：https://ac.nowcoder.com/acm/contest/5968/E 题目描述 牛牛在牛市的旅游纪念商店里面挑花了眼，于是简单粗暴的牛牛决定——买最受欢迎的就好了。但是牛牛的背包有限，他只能在商店的n个物品里面带m个回去，不然就装不下了。并且牛牛希望买到的纪念品不要太相似，所以
展开全文
解题思路 从排成一行的 n 个物品中选出 m 个，相邻物品的间隔必须 >= k。第 i+1 个物品的欢迎值为 popular[i]，求选出物品的总欢迎值最大是多少？ dp[i][j] 表示在前 j+1 个物品中，选出 i+1 个物品的最大总欢迎值。 如果不选第 j+1 个物品，dp[i][j
展开全文
大致题意
1.从n个物品中选出m个物品，使得值最大
2.任意两个物品之间的位置差 >= k（附加条件）
思路
首先可以看出贪心是不可以的，然后根据求最大值、最小值等关键字眼可以看出这是一道dp题，而且与背包dp板子相似
然后就是dp三件套 定义 初始化 状态转移方程
1.定义 因为最后要求的
展开全文
感觉是道比较简单的dp,但意外的比较容易做错，主要是细节很容易错。
状态表示：dp[i][j]来表示从前i个物品中取到j个能得到的最大受欢迎程度。
状态转移：对于第i个物品只有拿或者不拿两种选择，因为j我们保证一定能取这么多，所以如果拿第i个物品的话：
dp[i][j]=dp[i-k][j-1]+a
展开全文
牛牛的旅游纪念品
题目描述
牛牛在牛市的旅游纪念商店里面挑花了眼，于是简单粗暴的牛牛决定——买最受欢迎的就好了。
但是牛牛的背包有限，他只能在商店的n个物品里面带m个回去，不然就装不下了。
并且牛牛希望买到的纪念品不要太相似，所以导购小姐姐帮助牛牛把纪念品全部排成了一行，牛牛只需要让选出来要买的m个
展开全文
链接：https://ac.nowcoder.com/acm/contest/24213/1016
来源：牛客网
题目描述
牛牛在牛市的旅游纪念商店里面挑花了眼，于是简单粗暴的牛牛决定——买最受欢迎的就好了。
但是牛牛的背包有限，他
展开全文
牛牛的旅游纪念品 (nowcoder.com)
问题描述：一行有n个物品，要选m个，同时两个选的物品之间的间隔要大于等于k。求选m个的最大价值。
思路：线性dp。状态表示为：在第j个选了i个的最大价值。
转移方程：
k \quad max(F(i,j-1), F(i-1,j-k) + a[j])
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
