当前位置: 首页 > news >正文

牛客刷题-Day4

牛客刷题-Day4

今日刷题:\(1016-1020\)

1016 牛牛的旅游纪念品

题目描述

牛牛在牛市的旅游纪念商店里面挑花了眼,于是简单粗暴的牛牛决定——买最受欢迎的就好了。
但是牛牛的背包有限,他只能在商店的 \(n\) 个物品里面带 \(m\) 个回去,不然就装不下了。
并且牛牛希望买到的纪念品不要太相似,所以导购小姐姐帮助牛牛把纪念品全部排成了一行,牛牛只需要让选出来要买的 \(m\) 个物品中任意两个的位置差都大于等于 \(k\) 就行了。
现在告诉你这 \(n\) 个物品排成一行之后的受欢迎程度(可能是负数),求牛牛带回去的 \(m\) 个物品的最大欢迎度之和。

输入描述

第一行三个数 \(n,m,k\)
接下来一行,有 \(n\) 个整数,是 \(n\) 个物品按顺序的受欢迎程度。

输出描述

输出一个数为题目所求的最大和。

示例

输入

4 2 2
2 4 -6 1

输出

5
说明

\(𝑛≤10000,𝑚≤100\)\(𝑚≤𝑛\),答案保证在 int 范围内,保证按照题目要求一定能取到 \(m\) 个物品。

解题思路
  • 状态表示:\(f_{i,j}\) 表示前 \(i\) 个取 \(j\) 个的受欢迎度之和;
  • 状态计算:如果不购买第 \(i\) 个物品,\(f_{i,j}=f_{i-1,j}\);如果要购买,则 \(f_{i,j}=max(f_{i,j},f_{i-k,j-1}+a_i)\),取 \(i-k\) 保证两个物品相差大于等于 \(k\)
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 10010, M = 110;int n, m, k;
int a[N], f[N][M]; // f[i][j] 表示前 i 个取 j 个int main() {scanf("%d%d%d", &n, &m, &k);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);memset(f, 128, sizeof f);for (int i = 1; i <= n; i++) {f[i][1] = max(f[i - 1][1], a[i]);}for (int i = k + 1; i <= n; i++)for (int j = 2; j <= m; j++) {f[i][j] = f[i - 1][j];if (i - k >= 0)f[i][j] = max(f[i][j], f[i - k][j - 1] + a[i]);}cout << f[n][m] << endl;return 0;
}
http://www.hskmm.com/?act=detail&tid=16217

相关文章:

  • Skinned Mesh Renderer与LOD系统蒙皮变形异常全解析
  • K8S (Containerd)初始化安装流程
  • ?模拟赛 赛后总结
  • 日志|动态规划|最长回文子串|最长公共子序列|HTML CSS
  • Java 字段命名避坑: success和isSuccess
  • OTA升级时软件异常复位问题分析
  • Atcoder Educational DP Contest 做题记录
  • 20250924
  • 跨端边云时序数据管理新范式:Apache IoTDB 的 DB+AI 融合之道 - 实践
  • 《Real-Time Rendering》第二章 图形渲染管线
  • 放弃Unity后,我为什么选择了Unigine?
  • PHP 与 Java 的终极对比:2025年,开发者该如何选择? - 详解
  • 题单63——流程控制
  • 银行同业存单的信用等级
  • 软件技术基础第一次作业
  • 2025XDOJ个人题解——写在前面
  • 适合电子纸屏幕的简易象棋打谱程序
  • 0924
  • java_string比较中的细节
  • 扫描线学习笔记
  • go-reids
  • AI完美声音克隆及情绪控制,与真人无异,Lark下载介绍
  • WSL,适用于 Linux 的 Windows 子系统
  • 9-24
  • 代码随想录算法训练营第八天 |344.反转字符串、541. 反转字符串II、LCR 122. 路径加密
  • 9/24
  • 安装与卸载JDK8
  • mysql慢sql配置
  • Linux zdb -C (zfs Debugger调试器)
  • 从零开始实现简易版Netty(八) MyNetty 实现Small规格的池化内存分配