[USACO10OPEN] Cow Hopscotch G

The cows have reverted to their childhood and are playing a game similar to human hopscotch. Their hopscotch game features a line of N (3 <= N <= 250,000) squares conveniently labeled 1..N that are chalked onto the grass. Like any good game, this version of hopscotch has prizes! Square i is labeled with some integer monetary value V\_i (-2,000,000,000 <= V\_i <= 2,000,000,000). The cows play the game to see who can earn the most money. The rules are fairly simple: \* A cow starts at square '0' (located just before square 1; it has no monetary value). \* She then executes a potentially empty sequence of jumps toward square N. Each square she lands on can be a maximum of K (2 <= K <= N) squares from its predecessor square (i.e., from square 1, she can jump outbound to squares 2 or 3 if K==2). \* Whenever she wishes, the cow turns around and jumps back towards square 0, stopping when she arrives there. In addition to the restrictions above (including the K limit), two additional restrictions apply: \* She is not allowed to land on any square she touched on her outbound trip (except square 0, of course). \* Except for square 0, the squares she lands on during the return trip must directly precede squares she landed on during the outbound trip (though she might make some larger leaps that skip potential return squares altogether). She earns an amount of money equal to the sum of the monetary values of all the squares she jumped on. Find the largest amount of cash a cow can earn. By way of example, consider this six-box cow-hopscotch course where K has the value 3: ```cpp Square Num: 0 1 2 3 4 5 6 +---+ +---+ +---+ +---+ +---+ +---+ +---+ |///|--| |--| |--| |--| |--| |--| | +---+ +---+ +---+ +---+ +---+ +---+ +---+ Value: - 0 1 2 -3 4 5 ``` One (optimal) sequence Bessie could jump (shown with respective bracketed monetary values) is: 1[0], 3[2], 6[5], 5[4], 2[1], 0[0] would yield a monetary total of 0+2+5+4+1+0=12. If Bessie jumped a sequence beginning with 0, 1, 2, 3, 4, ... then she would be unable to return since she could not legally jump back to an untouched square. 奶牛们正在回味童年，玩一个类似跳格子的游戏，在这个游戏里，奶 牛们在草地上画了一行N个格子，(3 <=N <= 250,000)，编号为1..N。 就像任何一个好游戏一样，这样的跳格子游戏也有奖励！第i个格子标有一个数字V\_i(-2,000,000,000 <=V\_i <= 2,000,000,000)表示这个格子的钱。奶牛们想看看最后谁能得到最多的钱。 规则很简单： \* 每个奶牛从0号格子出发。(0号格子在1号之前，那里没钱) \* 她向N号格子进行一系列的跳跃(也可以不跳)，每次她跳到的格子最多可以和前一个落脚的格子差K格(1 <= K <= N)(比方说，当前在1号格，K=2, 可以跳到2号和3号格子) \*在任何时候，她都可以选择回头往0号格子跳，直到跳到0号格子。另外，除了以上规则之外， 回头跳的时候还有两条规则： \*不可以跳到之前停留的格子。 \*除了0号格子之外，她在回来的时候，停留的格子必须是恰巧过去的时候停留的某个格子的前一格(当然，也可以跳过某些过去…

\* Line 1: Two space separated integers: N and K \* Lines 2..N+1: Line i+1 contains a single integer: V\_i

\* Line 1: A single line with a single integer that is the maximum amount of money a cow can earn

6 3 
0 
1 
2 
-3 
4 
5 

12