题面描述

安全分析师小王正在开发一款先进的入侵检测系统（IDS），旨在实时监控网络流量并识别潜在的恶意活动。系统将网络抽象为一个下标从$0$开始的整数数组 node_scores，其中每个元素代表对应位置的安全评分：正值表示安全或有正面安全措施，负值表示存在潜在风险或威胁。 分析师从入口节点（下标$0$）开始，每一步最多可以前进$K$步，但不能超出数组边界。也就是说，如果当前位于下标$i$，则可以跳到任意下标$j$，满足

$i+1 \le j \le min(n-1,i+K)$

目标是到达下标$n-1$（最后一个监控点），并使累积的安全评分总和最大。注意：路径上的评分可能为正也可能为负。

思路

1. 记$dp[i]$为到达节点$i$时的最大累积安全得分，则期望： $dp[i]$ =$max_{j \in [i-K,i-1]}(dp[j])$ +node_scores[i].

2. 直接计算会导致每个$i$遍历$K$个前驱，整体时间$O(nK)$，在$n,K$均可达$10^5$ 时不可行。

3. 使用「单调队列」优化滑动窗口最大值的维护：维护一个双端队列 dq，其中保存候选下标，并保持对应的$dp$值递减。

   • 维护队首始终是窗口内最大的$dp$下标；
   • 当处理到$i$时，将不在窗口 $[i-K,i-1]$ 的下标从队首或队尾剔除；
   • 利用队首的$dp$值计算 $dp[i]$，再将$i$插入队列时，从队尾剔除所有$dp$值不大于 $dp[i]$的下标，保证队列单调递减。

4. 这样每个元素进出队列各一次，整体时间$O(n)$，空间$O(n)$。

C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int K, n;
    cin >> K >> n;
    vector<int> node_scores(n);
    for (int i = 0; i < n; i++) {
        cin >> node_scores[i];
    }

    // dp[i] 表示到达节点 i 时的最大安全得分
    vector<long long> dp(n, LLONG_MIN);
    dp[0] = node_scores[0];

    deque<int> dq;
    dq.push_back(0);  // 双端队列中存放下标，并保持 dp[dq] 递减

    for (int i = 1; i < n; i++) {
        // 剔除队首中不在窗口 [i-K, i-1] 的下标
        while (!dq.empty() && dq.front() < i - K) {
            dq.pop_front();
        }
        // 当前 dp 转移：使用窗口最大值 + 当前节点分数
        dp[i] = dp[dq.front()] + node_scores[i];

        // 插入 i，保持队列单调递减
        while (!dq.empty() && dp[dq.back()] <= dp[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
    }

    cout << dp[n-1] << "\n";
    return 0;
}

Python

import sys
from collections import deque

def max_score(node_scores, K):
    n = len(node_scores)
    dp = [-10**18] * n  # 初始化为足够小的值
    dp[0] = node_scores[0]

    dq = deque([0])  # 存放下标，维护 dp 递减

    for i in range(1, n):
        # 移除过期的窗口左侧下标
        while dq and dq[0] < i - K:
            dq.popleft()
        # 转移方程
        dp[i] = dp[dq[0]] + node_scores[i]
        # 维护单调队列
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()
        dq.append(i)

    return dp[-1]

if __name__ == "__main__":
    data = sys.stdin.read().split()
    K = int(data[0])
    n = int(data[1])
    scores = list(map(int, data[2:2+n]))
    print(max_score(scores, K))

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int K = Integer.parseInt(br.readLine().trim());
        int n = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        long[] dp = new long[n];
        int[] nodeScores = new int[n];
        for (int i = 0; i < n; i++) {
            nodeScores[i] = Integer.parseInt(st.nextToken());
        }

        // 初始化 dp 数组
        Arrays.fill(dp, Long.MIN_VALUE);
        dp[0] = nodeScores[0];

        Deque<Integer> dq = new ArrayDeque<>();
        dq.addLast(0);  // 存放下标，dp 递减

        for (int i = 1; i < n; i++) {
            // 移除窗口外的下标
            while (!dq.isEmpty() && dq.peekFirst() < i - K) {
                dq.pollFirst();
            }
            // 状态转移
            dp[i] = dp[dq.peekFirst()] + nodeScores[i];
            // 维护单调队列
            while (!dq.isEmpty() && dp[dq.peekLast()] <= dp[i]) {
                dq.pollLast();
            }
            dq.addLast(i);
        }

        System.out.println(dp[n-1]);
    }
}

题目内容

安全分析师小王正在开发一款先进的入侵检测系统 （IDS），旨在实时监控网络流量并失败潜在的恶意活动；如何在一个复杂的网络环境中，从起始节点出发，到达终端节点（即最后一个监控点），同时最大化累积的安全评分。

在这个系统中，整个网络被抽象为一个下标从 $0$ 开始的整数数组 $node$ _$scores$ ，其中每个元素代表对应位置的安全评分。正值表示该位置是安全的或有正面的安全措施，而负值则表示存在潜在风险或威胁。分析师开始于位置 $0$ （入口节点），每一步可以前进最多 k 步，但不能超出数组边界。也就是说，如果当前位于下标 $i$ ，则可以选择跳到 $[i+1,min(n-1,i+k)]$ 包含两个端点的任意位置。目标是到达数组的最后一个位置（即最后一个监控点，下标为 $n-1$ ），并且在此过程中最大化累积的安全评分得分。这里的得分可以是正也可以是负，取决于路径上遇到的安全状况。

具体任务是编写一个算法，给定一个整数数组 $node$ _$scores$ 和一个整数 $k$ ，该算法应返回能够获得的最大得分。这个得分是通过选将一条从起点到终点的最佳路径来实现的，这条路径上的所有数字之和即为最大得分，即使某些位置的安全评分为负。

输入描述

每组数据第一行为最大的进步数 $k$ ，第二行为节点数量 $n$ ，第三行的 $n$ 个数为每个节点的安全得分

输入范围限制：

• $1 <= node$ _$scores.length,k <=100000$

• $-10000<= node$ _$scores[i]<= 10000$

输出描述

到达最后一个节点时可以获得的最大安全得分

样例1

输入

2
8
3 -5 -10 2 -1 5 -6 -5

输出

0

说明

最多可前进步数 $k=2$ ，安全评分数组长度 $n=8$ ，数组 $nodes$ _$cores$ 的具体值为 $=[3,-5,-10,2,-1,5,-6,-5]$ ，可使安全评分最大的子字列 $[3,-5,2,5,-5]$ ，因此最大安全得到为 $0$

样例2

输入

3
6
1 -5 -2 4 0 7

输出

12

说明

最多可前进步数 $k=3$ ，安全评分数组长度 $n=6$ ，数组 $nodes$ _$cores$ 的具体值为 $=[1,-5,-2,4,0,7]$ ，可使安全评分最大的子字列 $[1,4,7]$ ，因此最大安全得到为 $12$

样例3

输入

2
6
1 -3 -2 4 -7 5

输出

8

说明

最多可前进步数 $k=2$ ，安全评分数组长度 $n=6$ ，数组 $nodes$ _$cores$ 的具体值为 $=[1,-3,-2,4,-7,5]$ ，可使安全评分最大的子字列 $[1,-2,4,5]$ ，因此最大安全得到为 $8$