题目(团内题,外人查看不了,就不放链接了):

---

【FCOI #8】最大子段和

题目背景

本题目含有 Extra 分数，分值为正常满分的 150%

题目描述

给定长度为 $N$ 的整数序列 $A$，请在里面选出长度为 $K$ 且不重叠的两段（要连续），满足和最大，求出最大值。

形式化的说，你要找到两个正整数 $(i, j)$，满足 $j \ge i + k, j + k - 1 \le n$，求出 $A_i + A_{i+1} + \dots + A_{i + k-1} + A_j + A_{j+1} + \dots + A_{j+k-1}$ 的最大值。

输入格式

格式如下：

N K
A_1 A_2 A_3 ... A_N

输出格式

一个整数，表示答案。

样例 #1

样例输入 #1

6 2
9 3 -1 20 -3 3

样例输出 #1

31

样例 #2

样例输入 #2

9 2
-1000 3 2 -1000 9 8 -1000 5 2

样例输出 #2

24

样例 #3

样例输入 #3

10 5
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

样例输出 #3

10000000000

样例 #4

样例输入 #4

20 4
-3 9 -9 10 -3 -1 -3 3 7 -9 -4 -1 9 -9 2 -3 -5 -10 -8 -9

样例输出 #4

13

样例 #5

样例输入 #5

2 1
-1 -1

样例输出 #5

-2

提示

数据范围

对于 70% 的数据，保证 $N \le 20$

对于 100% 的数据，保证 $2 \times K \le N \le 100, -10^{9} \le A_i \le 10^{9}$

K 是不为零的数字。

Extra 数据范围

对于 100% 的数据，保证 $2 \times K \le N \le 2 \times 10^{5}, -10^{9} \le A_i \le 10^{9}$

K 是不为零的数字

样例解释 1

选择 $\{9, 3\}$， $\{-1, 20\}$ 两段，和为 31。

两段连续子序列可以相邻，但是不能重叠，也就不能选择 $(\{-1, 20\}, \{20, -3\})$ 这一组方案。

样例解释 2

选择 $\{9, 8\}$， $\{5, 2\}$ 两段，和为 24。

这一组样例就是不相邻的解。

---

这题的动态转移方程是啥呀?暴力搜索 Extra 数据 通不过