采集（collect）

解题思路

按后缀动态规划。设dp[t][i]表示只考虑资源点i～n、最多还能选t个时的最大价值。当前位置有两种选择：

1. 不选i，收益为dp[t][i+1]。
2. 选i，获得v[i]，下一次只能从next[i]=min(n+1,i+c[i]+1)开始，收益为v[i]+dp[t-1][next[i]]。

因此dp[t][i]=max(dp[t][i+1],v[i]+dp[t-1][next[i]])。先按t从1增加到k，每轮i从n递减到1。只需保存前后两行，把O(nk)空间降至O(n)。

正确性说明

最优方案要么不包含i，要么包含i，二者互斥且覆盖全部。包含i后所有i+1～i+c[i]不可选，剩余正好是next[i]起的子问题且次数减1。对两类最优值取最大得到当前最优。t=0或i=n+1都不能再产生收益，边界为0。按上述顺序所有依赖都已计算，故最终dp[k][1]正确。

易错点

“最多k个”允许少选，所有边界初值为0；选中后跳过c[i]个，因此next必须再加1；v累计可能达10^11，用long long。

复杂度

时间O(nk)，空间O(n)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<long long> value(n + 2);
    vector<int> next(n + 2);
    for (int i = 1; i <= n; i++)
        cin >> value[i];
    for (int i = 1; i <= n; i++) {
        int c;
        cin >> c;
        next[i] = min(n + 1, i + c + 1);
    }
    vector<long long> previous(n + 2), current(n + 2);
    for (int t = 1; t <= k; t++) {
        current[n + 1] = 0;
        for (int i = n; i >= 1; i--)
            current[i] = max(current[i + 1], value[i] + previous[next[i]]);
        previous.swap(current);
    }
    cout << previous[1] << "\n";
    return 0;
}