链接：https://ac.nowcoder.com/acm/contest/24213/1016
来源：牛客网

题目描述

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

输入描述: 

		

			 第一行三个数n,m,k
		


		

			 接下来一行,有n个整数,是n个物品按顺序的受欢迎程度。

输出描述: 

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

题型：

动态规划--求最大值--选或不选物品问题+选的物品之间存在固定间隔

思路：

1.明确总问题：求n个物品中选m个物品的最大欢迎度之和，且选的m个物品中任意两个的位置差都大于等于k
2.明确子问题：求i个物品中选j个物品的最大欢迎度之和，且选的j个物品中任意两个的位置差都大于等于k
3.明确dp对象：设dp[i][j]为选到了第i个物品时，已经选了j个物品，那么最终答案的值就为dp[n][m]
4.明确状态转移方程：当遇到第i个物品时，我们可以选择选或不选，如果不选的话，那么dp[i][j]=dp[i-1][j]
如果选的话，那么dp[i][j]=dp[i-k][j-1]+a[i];（这个式子来源：我们知道，如果不选的话，dp[i][j]=max(dp[i-k][j-1],dp[i-k-1][j-1],dp[i-k-2][j-1],......,dp[k+2][j-1],dp[k+1][j-1],dp[k][j-1])+a[i]，又由于dp[i-k][j-1]>=dp[i-k-1][j-1]>=dp[i-k-2][j-1]>=......>=dp[k+1][j-1]>=dp[k][j-1]，所以取max后的值一定等同于dp[i-k][j-1]的值）
5.明确初始化：一要注意，由于数据有负数，所以dp数组初始化为负数，二要注意选第一个物品时需要单独初始化，即dp[i][1]=max(a[i],dp[i-1][1]); //相当于找前i个物品中的最大欢迎值
6.明确i,j范围:i:k->n（i从k开始是因为双重for循环这里是开始找第2~m个物品了，所以前k个物品肯定不能选，因为有间隔）    
j:2->m（因为j=1已经在初始化的时候遍历过一次了，不需要重复遍历）

代码1： 

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
ll a[10200],dp[10200][120];
int main(){
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++){
			dp[i][j]=-999999999999;
		}
	}
	for(int i=1;i<=n;i++){
		dp[i][1]=max(a[i],dp[i-1][1]);
	}
	for(int i=k;i<=n;i++){
		for(int j=2;j<=m;j++){
			dp[i][j]=max(dp[i-1][j],dp[i-k][j-1]+a[i]);
		}
	}
	printf("%lld\n",dp[n][m]);
	return 0;
}
当然也可以把i和j的位置倒转过来

代码2： 

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
ll a[10200],dp[120][10200];
int main(){
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	for(int i=0;i<=m;i++){
		for(int j=0;j<=n;j++){
			dp[i][j]=-999999999999;
		}
	}
	for(int j=1;j<=n;j++){
		dp[1][j]=max(a[j],dp[1][j-1]);
	}
	for(int i=2;i<=m;i++){
		for(int j=k;j<=n;j++){
			dp[i][j]=max(dp[i][j-1],dp[i-1][j-k]+a[j]);
		}
	}
	printf("%lld\n",dp[m][n]);
	return 0;
}