牛牛的旅游纪念品

先看题目：https://ac.nowcoder.com/acm/contest/5968/E
题目描述：
n个物品中挑选m个物品，任意两个物品的位置差大于等于k，求最大受欢迎度。
解题思路：
背包问题，让求n个物品中挑m个物品的最大受欢迎度，跟据题意，设f[i][j]是前i个物品挑选j个的最大受欢迎度，转移方程：f[i][j] = max{f[i-1][j], f[i-k][j-1]+a[i]}
这道题在编程实现上有很多需要注意与理解的地方：
1.由于欢迎度可以是负数，因此，dp[][]应当初始化为负无穷。
2.由于1，因此跟据状态转移方程的写法，无法通过dp[0][]一步步转移得来，因此需要初始化dp[][1]，从而才能转移得到其他状态。
3.由于从关于j-1的状态转移得到关于j的状态，因此需要将for(j)在外面，for(i)套在里面。
4.j从2开始是因为j==1的状态已经提前被初始化了，i从k+1开始是因为既然j从2开始，不可能再取到<=k的数。当然表格中这些非法的状态被标为了负无穷，并不会影响到中间和最终的结果。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[10010];
int dp[10010][1000];
int main()
{
    int n, m, k;
    int ma = -0x7f;
    memset(dp, -0x7f, sizeof(dp));
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 1; i <= n; i++) {
        scanf("%d",&a[i]);
        dp[i][1] = max(dp[i-1][1],a[i]);
    }
    for(int j = 2; j <= m; j++) {
        for(int i = k+1; i <= n; i++) {
            dp[i][j] = max(dp[i-1][j], dp[i-k][j-1]+a[i]);
        }
    }
    printf("%d\n",dp[n][m]);
}