这道题的正解是 单调队列优化DP,但是我们用朴素解法 枚举窗口最大值 也能在考试时拿到一定的分数。
题意:从下标 0 跳到 n−1,每次最多前进 K 步,路径上分数之和最大(分数可正可负)。
设 dp[i] 为到达下标 i 时的最大累计得分,则:
dp[i]=j∈[i−K,i−1]maxdp[j]+node_scores[i]小明正在开发一套入侵检测系统(IDS),用于实时监控网络流量并识别潜在威胁。他将整个网络建模为一个从 0 开始编号的整数数组 node_scores,其中每个位置对应一个监控节点,数组元素值表示该节点的安全评分。安全评分可以为正、零或负:正数表示该节点具有正向安全措施,负数表示该节点存在风险或威胁。
分析节点从下标 0 的入口节点出发,目标是到达数组的最后一个节点。移动时必须遵守以下规则:如果当前位于下标 i,下一步只能跳到区间 [i+1,min(n−1,i+k)] 内的任意一个下标。也就是说,每次至少前进 1 个节点,至多前进 k 个节点,并且不能越过数组末尾。
一条路径的累积安全评分定义为路径上经过的所有节点的安全评分之和,包括起点和终点。给定数组 node_scores 和整数 k,请计算从入口节点到最后一个节点能够获得的最大累积安全评分。
约束条件:
node_scores 的长度 n 和最大步数 k 均在 1 到 100000 之间。node_scores 中每个元素的值均在 -10000 到 10000 之间。
© CodeFun2000 · 使用条款
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册