cswork / OA打开练习工作台

JPMorgan ChaseOA #2

Network Compromise Max Value Sum

估计中等评测数据准备中,可先阅读题面

考点(AI 标注)动规入门

You are given a computer network with n servers numbered from 1. Each server has a security value sec[i] (positive or negative). A hacker starts at one of these servers and jumps through the network. From node x, the hacker can jump to node (x + k). If (x + k) exceeds n, the hacker's attack ends. The hacker's goal is to maximize the sum of the security values of the compromised servers (initially 0 with 0 servers).

Choose the optimal starting node and return the maximum security value sum.

Example

sec = [2, -3, 5, -1, 4], k = 2
Start 0: visit 0,2,4 -> running sums 2, 7, 11; best 11.
Start 1: visit 1,3 -> running sums -3, -4; best 0.
Answer: 11