Circular Barn

题目描述

作为现代建筑的爱好者，农夫约翰建造了一个新谷仓，其形状是一个完美的圆。谷仓内部由一个包含 $n$ 个房间的环组成，房间沿着谷仓周边按顺时针方向编号为 $1 \ldots n$（$3 \leq n \leq 1,000$）。每个房间都有通往相邻两个房间的门，并且还有一扇通向谷仓外部的门。 农夫约翰希望最终恰好有 $r_i$ 头牛待在房间 $i$ 中（$1 \leq r_i \leq 1,000,000$）。为了有序地把牛赶进谷仓，他计划解锁 $k$ 扇外部的门（$1 \leq k \leq 7$），让牛只能从这些门进入。每头牛进入后会沿顺时针方向穿过房间，直到到达一个合适的目的地。农夫约翰希望选择解锁哪些外部的门，使得他的牛在进入谷仓后总体行走的总距离最小（牛可以在谷仓外的这 $k$ 扇解锁门前以任意方式排队；这不计入所讨论的总距离）。请确定：如果他选择最优的 $k$ 扇门解锁，牛需要行走的最小总距离是多少。

输入格式

第一行输入包含 $n$ 和 $k$。接下来的 $n$ 行每行包含 $r_1 \ldots r_n$。

输出格式

请输出牛需要行走的最小总距离。

6 2
2
5
4
2
6
2

14

提示

农夫约翰可以解锁 2 号门和 5 号门。11 头牛从 2 号门进入，走到房间 2、3 和 4 的总距离为 8。10 头牛从 5 号门进入，走到房间 5、6 和 1 的总距离为 6。 题目致谢：Brian Dean

标签: USACO|2016|Platinum

来源

USACO|2016|Platinum