1537 - 圆环取数
Time Limit : 2 Second
Memory Limit : 256 MB
Submission: 13
Solved: 2
- Description
- 【问题背景】
Yy攒足了路费来到了宫殿门前，但是当yy要进去的时候，却发现了要与守护者进行一个特殊的游戏，只有取到了最大值才能进去……
【问题描述】
守护者拿出被划分为n个格子的一个圆环，每个格子上都有一个正整数，并且定义两个格子的距离为两个格子之间的格子数的最小值。环的圆心处固定了一个指针，一开始指向了圆环上的某一个格子，你可以取下指针所指的那个格子里的数以及与这个格子距离小于k的格子的数，取一个数的代价即这个数的值。指针是可以转动的，每次转动可以将指针由一个格子转向其相邻的格子，且代价为圆环上还剩下的数的最大值。
现在对于给定的圆环和k，求将所有数取完所有数的最小代价。
- Input
- 多组数据，每组的第1行有两个正整数n和k，描述了圆环上的格子数与取数的范围。
第2行有n个正整数，按顺时针方向描述了圆环上每个格子上的数，且指针一开始指向了第1个数字所在的格子。
所有整数之间用一个空格隔开，且不超过10000。
- Output
- 每组数据输出一行，仅包括1个整数，为取完所有数的最小代价。
- sample input
-
6 1 4 1 2 3 1 3
- sample output
-
21
- hint
- 第一步不转动指针，取走4、3两个数，代价为7；
第2步指针顺时针转动2格，圆环上最大数为3，代价为6，取走1、2、3三个数，代价为6；
第3步指针顺时针转动1格，代价为1，取走剩下的一个数1，代价为1；
最小代价为7+6+6+1+1=21。
n≤2000，k≤500；
- source
- “恒生杯”网络预选赛 | 非原创