链接：https://ac.nowcoder.com/acm/contest/5968/E

题目描述

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

输入描述:

第一行三个数n,m,k

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

输出描述:

输出一个数为题目所求的最大和
示例1
输入
4 2 2
2 4 -6 1
输出
5

#include<iostream> 
#include<string.h>
#include<cmath>
using namespace std;

int w[10005],dp[105][10005];
int main()
{
    int n,m,k,ma=-0x3f;
    cin>>n>>m>>k;
    memset(dp,-0x3f,sizeof(dp));
    for(int i=1;i<=n;i++){
        cin>>w[i];
        ma=max(ma,w[i]);//记录价值最大的 
        dp[1][i]=max(dp[1][i-1],w[i]);//前i个价值最大的 
    }
    if(m==1){
        cout<<ma;
        return 0;
    }//如果只带回一个，那么输出价值最大的即可
    for(int i=2;i<=m;i++){
        for(int j=k+1;j<=n;j++){
            dp[i][j]=max(dp[i][j-1],dp[i-1][j-k]+w[j]);
        }//因为选择的相邻两个物品的距离至少为k,所以j从k+1枚举即可 
    }//如果带回大于一个，dp求j个物品带回i个的最大价值 
    cout<<dp[m][n];
    return 0;
}