牛牛的旅游纪念品

解题思路

从排成一行的 n 个物品中选出 m 个，相邻物品的间隔必须 >= k。
第 i+1 个物品的欢迎值为 popular[i]，求选出物品的总欢迎值最大是多少？

dp[i][j] 表示在前 j+1 个物品中，选出 i+1 个物品的最大总欢迎值。

1. 如果不选第 j+1 个物品，dp[i][j] = dp[i][j-1]；
2. 如果选了第 j+1 个物品，dp[i][j] = max(dp[i-1][j-k], dp[i-1][j-k-1], ..., dp[i-1][0]) + popular[j]。
   因为 dp[i-1][j-k] >= dp[i-1][j-k-1] >= ... >= dp[i-1][0]，所以 dp[i][j] = dp[i-1][j-k] + popular[j]。

选取两种方案中欢迎值的最大值。最后的 dp[m-1][n-1] 即为所求。

C++代码

#include<cstdio>
#include<vector>
#include<limits.h>
using namespace std;

int main(){
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    vector<int> popular(n);
    for(int i=0; i<n; ++i)
        scanf("%d", &popular[i]);
    vector<vector<int>> dp(m, vector<int>(n, INT_MIN));
    dp[0][0] = popular[0];
    for(int j=1; j<n; ++j)
        dp[0][j] = max(dp[0][j-1], popular[j]);
    for(int i=1; i<m; ++i){
        for(int j=i*k; j<n; ++j){
            dp[i][j] = max(dp[i][j-1], dp[i-1][j-k] + popular[j]);
        }
    }
    printf("%d\n", dp[m-1][n-1]);
    return 0;
}