Problem5389--时代

5389: 时代

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

老师给定你 $n$ 个数字 {$a_n$} 和参数 $m$,$k$,她想让你选出一些数。
选择一个数 $a_i$ 的花费为 $a_i^2+max(m-i+j,0)^2$,$a_j$ 为上一次选择的数(不存在则为 $0$)。
请你选出 $k$ 个给定数字,使得总花费最小。

Input

输入共两行。
第一行输入三个正整数 $n,m,k$。$n,k,a_i\leq 1000$,$m≤100$。
第二行输入 $n$ 个正整数 $a_i$。$a_i\leq 1000$。

Output

输出共一行一个整数,表示最小花费。

Sample 1 Input

10 3 5
1 1 4 5 1 4 1 9 1 9

Sample 1 Output

15

HINT

【样例说明】
最优方案为选择 $a_1,a_2,a_5,a_7,a_9$。

Source/Category

基础算法 4.120.动态规划