/ OIer TK / 题库 /

圆环取数

圆环取数

测试数据来自 system/1451

背景

小K攒足了路费来到了教主所在的宫殿门前,但是当小K要进去的时候,却发现了要与教主守护者进行一个特殊的游戏,只有取到了最大值才能进去Orz教主……

描述

守护者拿出被划分为n个格子的一个圆环,每个格子上都有一个正整数,并且定义两个格子的距离为两个格子之间的格子数的最小值。环的圆心处固定了一个指针,一开始指向了圆环上的某一个格子,你可以取下指针所指的那个格子里的数以及与这个格子距离不大于k的格子的数,取一个数的代价即这个数的值。指针是可以转动的,每次转动可以将指针由一个格子转向其相邻的格子,且代价为圆环上还剩下的数的最大值。

现在对于给定的圆环和k,求将所有数取完所有数的最小代价。

格式

输入格式

输入的第1行有两个正整数n和k,描述了圆环上的格子数与取数的范围。

第2行有n个正整数,按顺时针方向描述了圆环上每个格子上的数,且指针一开始指向了第1个数字所在的格子。

所有整数之间用一个空格隔开,且不超过10000。

输出格式

输出仅包括1个整数,为取完所有数的最小代价。

样例1

样例输入1

6 1
4 1 2 3 1 3

样例输出1

21

限制

对于20%的数据,n≤10,k≤3;
对于40%的数据,n≤100,k≤10;
对于60%的数据,n≤500,k≤20;
对于100%的数据,n≤2000,k≤500;

时限1s。

提示

考虑向右为顺时针。
第一步不转动指针,取走4、3两个数,代价为7;
第2步指针顺时针转动2格,圆环上最大数为3,代价为6,取走1、2、3三个数,代价为6;
第3步指针顺时针转动1格,代价为1,取走剩下的一个数1,代价为1;
最小代价为7+6+6+1+1=21。

信息

ID
1422
难度
(无)
分类
动态规划 | 环形DP 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者