牛客刷题-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;
}