1.题目相关
-
标签：
DP单调队列优化 - 题目地址：不是VIP没法看。。。。
- 题目大意：给定N和K，表示有N个数，在其中选取连续的几段，且长度不能大于K。问所选数的和最大能为多少。
2.思路
- 很简单的DP。sum[i]表示前缀和，dp[i]表示选第i个数时的最优方案。
- dp[i] = max{dp[j]+sum[i]-sum[j+1]} j∈[i-k-1,i-1)
- 那么思路就很明确了，对于dp[j]-sum[j+1]，用一个位置递增，值递减的单调队列维护，当i-j>k的时候就h++。
BZOJ_2442 修剪草坪
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。
推荐阅读更多精彩内容
- 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪：刷leetcod...
- 前言 转眼已经到5月，可是我还没订17年的计划，真是悲伤的故事。今年还是想花点时间，玩玩题目。题目不会太简单，也不...
