洛谷P2034题解：选择数字问题的最优解法

一、问题分析

题目要求在n个数字中选择若干数字，要求不能选择超过k个连续的数字，使得选中的数字之和最大。这是一个典型的动态规划问题，但需要特殊的优化技巧。

二、算法核心思路

1. 前缀和预处理：快速计算任意区间的和

2. 动态规划定义：

• DP[i]表示前i个数字的最大和

• 使用单调队列维护最优决策点

3. 单调队列优化：

• 维护一个递减队列

• 保证决策点不超过k的限制

三、完整代码实现（带注释）

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

int main() {
    ios::sync_with_stdio(false);  // 加速输入输出
    cin.tie(nullptr);             // 解除cin与cout的绑定
    
    int n, k;
    cin >> n >> k;
    vector<long long> a(n + 1), prefix(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        prefix[i] = prefix[i - 1] + a[i]; // 计算前缀和
    }
    
    vector<long long> dp(n + 2, 0); // dp[i]表示前i个数的最大和
    deque<int> q; // 单调队列维护最优决策点
    
    // 初始条件：不选任何数时和为0
    q.push_back(0);
    
    for (int i = 1; i <= n + 1; ++i) {
        // 维护队列头部，确保不超过k的限制
        while (!q.empty() && q.front() < i - k - 1) {
            q.pop_front();
        }
        
        // 状态转移：dp[i] = max(dp[j-1] - prefix[j]) + prefix[i-1]
        dp[i] = dp[q.front()] + prefix[i - 1] - prefix[q.front()];
        
        // 维护队列单调性
        while (!q.empty() && dp[i] - prefix[i] >= dp[q.back()] - prefix[q.back()]) {
            q.pop_back();
        }
        
        q.push_back(i);
    }
    
    cout << dp[n + 1] << endl;
    return 0;
}