题解 | #牛牛的旅游纪念品#

牛牛的旅游纪念品 (nowcoder.com)

问题描述：一行有n个物品，要选m个，同时两个选的物品之间的间隔要大于等于k。求选m个的最大价值。

思路：线性dp。状态表示为：在第j个选了i个的最大价值。

转移方程：

状态表示：F(i,j)表示在选了第j个物品后选了i个物品的最大价值。

如果i = 1，对于位置j来说有两个状态，要么选j的物品，要么不选就是前面的最大的物品。如果i > 1 && j > k，对于j也有两个状态，要么选，要么不选，跟i = 1的方式类似。

i = 1 和 i != 1的处理是类似的，但是由于边界的存在，让i = 1的处理变得特殊了。（

边界：

目标：

代码：

const int N = 1e4 + 21;
int f[121][N];
int a[N];
void solve() {
    int n,m,k; cin>>n>>m>>k;
    // 边界处理
    memset(f, -0x3f, sizeof(f));
    rep(i,1,n) {
        cin>>a[i];
    }
    rep(i,1,m) {
        rep(j,1,n) {
            // 如果i = 1，选了一个，要么是前面的，要么是当前位置物品
            if(i == 1) f[i][j] = max(f[i][j-1], a[j]);
            // 如果 j > k，要么不选 - f[i][j-1]，要么选 - f[i-1][j-k] + a[j]
            else if(j > k) f[i][j] = max(f[i][j-1], f[i-1][j-k] + a[j]);
        }
    }
    // 目标
    cout<<f[m][n];
}