#2001. [APIO2014] 序列分割

[APIO2014] 序列分割

题目描述

你正在玩一个关于长度为 nn 的非负整数序列的游戏。这个游戏中你需要把序列分成 k+1k + 1 个非空的块。为了得到 k+1k + 1 块,你需要重复下面的操作 kk 次:

选择一个有超过一个元素的块(初始时你只有一块,即整个序列)

选择两个相邻元素把这个块从中间分开,得到两个非空的块。

每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。

输入格式

第一行包含两个整数 nnkk。保证 k+1nk + 1 \leq n

第二行包含 nn 个非负整数 a1,a2,,ana_1, a_2, \cdots, a_n (0ai104)(0 \leq a_i \leq 10^4),表示前文所述的序列。

输出格式

第一行输出你能获得的最大总得分。

第二行输出 kk 个介于 11n1n - 1 之间的整数,表示为了使得总得分最大,你每次操作中分开两个块的位置。第 ii 个整数 sis_i 表示第 ii 次操作将在 sis_isi+1s_{i + 1} 之间把块分开。

如果有多种方案使得总得分最大,输出任意一种方案即可。

7 3
4 1 3 4 0 2 3
108
1 3 5

提示

你可以通过下面这些操作获得 108108 分:

初始时你有一块 (4,1,3,4,0,2,3)(4, 1, 3, 4, 0, 2, 3)。在第 11 个元素后面分开,获得 4×(1+3+4+0+2+3)=524 \times (1 + 3 + 4 + 0 + 2 + 3) = 52 分。

你现在有两块 (4),(1,3,4,0,2,3)(4), (1, 3, 4, 0, 2, 3)。在第 33 个元素后面分开,获得 (1+3)×(4+0+2+3)=36(1 + 3) \times (4 + 0 + 2 + 3) = 36 分。

你现在有三块 (4),(1,3),(4,0,2,3)(4), (1, 3), (4, 0, 2, 3)。在第 55 个元素后面分开,获得 (4+0)×(2+3)=20(4 + 0) \times (2 + 3) = 20 分。

所以,经过这些操作后你可以获得四块 (4),(1,3),(4,0),(2,3)(4), (1, 3), (4, 0), (2, 3) 并获得 52+36+20=10852 + 36 + 20 = 108 分。

限制与约定

第一个子任务共 11 分,满足 1k<n101 \leq k < n \leq 10

第二个子任务共 11 分,满足 1k<n501 \leq k < n \leq 50

第三个子任务共 11 分,满足 1k<n2001 \leq k < n \leq 200

第四个子任务共 17 分,满足 $2 \leq n \leq 1000, 1 \leq k \leq \min\{n - 1, 200\}$。

第五个子任务共 21 分,满足 $2 \leq n \leq 10000, 1 \leq k \leq \min\{n - 1, 200\}$。

第六个子任务共 29 分,满足 $2 \leq n \leq 100000, 1 \leq k \leq \min\{n - 1, 200\}$。

感谢@larryzhong 提供的加强数据