D. 魔法环

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

小 M 面临着激发自己魂器——魔法环的任务。

魔法环上有 n 个节点,每个节点上都有一个魔法精灵,每个魔法精灵都有一个固定的魔供值,这些魔供值形成一个 0 \sim n-1 的排列。

小 M 可以选择激活或不激活一个魔法精灵,但为了激发魔法环,必须至少激活 k(\ge 2) 个魔法精灵。

每个魔法精灵无论是否激活都会产生附魔值

  • 对于一个被激活的魔法精灵,它产生的附魔值为它的魔供值的平方
  • 对于一个未被激活的魔法精灵,它会在环上朝左右看,分别看向两边最近的被激活的魔法精灵。它会选择其中魔供值较大的一个作为「目标精灵」,产生的附魔值为这个「目标精灵」的魔供值与看向这个「目标精灵」时视线经过的距离乘积

作为新手,小 M 希望在激活魔法环的前提下,使得所有魔法精灵的附魔值之和最小,从而更好地控制魔法环的能量。

输入格式

输入格式

第一行两个整数 n,k

第二行 n 个整数,表示每个节点上魔法精灵的魔供值。

输出格式

输出格式

一行一个整数,表示最小附魔值之和。

样例

样例 #1

样例输入 #1

5 2
3 0 1 4 2

样例输出 #1

7

样例 #2

样例输入 #2

10 3
2 0 1 5 8 3 4 9 6 7

样例输出 #2

53

数据范围与提示

对于所有数据, 2\le k \le n \le 3000 k \le 100 ,每个节点上魔法精灵的魔供值形成一个 0\sim n-1 的排列。

Subtask n k\le 分值
1 10 13
2 100 100 17
3 300 21
4 1000 23
5 3000 26

【样例 1 解释】*

激活魔供值为 0 1 的魔法精灵。

  • 魔供值为 3 的魔法精灵,选择魔供值为 1 的魔法精灵,产生的附魔值为 1 \times 3 = 3
  • 魔供值为 0 的魔法精灵被激活,产生的附魔值为 0^2=0
  • 魔供值为 1 的魔法精灵被激活,产生的附魔值为 1^2=1
  • 魔供值为 4 的魔法精灵,选择魔供值为 1 的魔法精灵,产生的附魔值为 1 \times 1 = 1
  • 魔供值为 2 的魔法精灵,选择魔供值为 1 的魔法精灵,产生的附魔值为 1 \times 2 = 2

总共产生的附魔值为 7