1058: 不降序列

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:29 Solved:19

Description

给定一个长度为$n$的不降序列$a$,第一个元素为$a_1$,现在你可以执行以下操作至多$k$次: 假设此时序列长度为$m$,在$[2,m−1]$中选择一个整数$i$,将$a_i$删除**或**将其修改为任意数字(可以是自身)但依然需要保证序列为不降的。 最终序列(假设长度为$m$)的权值为相邻元素的差的平方,即: $$\sum_{i=1}^{m-1}(a_{i+1} - a_i)^2$$ 请问怎么操作可以使得最终权值最大?输出最大的最终权值。 ### 输入格式 第一行两个整数$n, k$。$(2 \le n \le 500, 0 \le k \le n - 2)$ 第二行$n$个整数表示序列$a$。$(1 \le a_i \le 10^9)$ 保证给定的$a_i$是不降的。 ### 输出格式 一个整数表示答案。 ### 样例输入 ``` 5 2 1 3 5 8 11 ``` ### 样例输出 ``` 68 ```