Circular Barn Revisited

题目描述

在上一次关于 Farmer John 的环形牛棚的闹剧之后，人们本以为他已经从这种非传统建筑中吸取了教训。然而，他认为只要允许每个房间进入多头奶牛，他仍然可以让他的环形牛棚（上一题中的牛棚）正常运作。

回顾一下：牛棚由一个包含 $n$ 个房间的环组成，房间沿牛棚外围按顺时针方向编号为 $1 \ldots n$（$3 \leq n \leq 100$）。每个房间都有通向其相邻两个房间的门，并且还有一扇通向牛棚外部的门。Farmer John 希望最终在房间 $i$ 中恰好有 $r_i$ 头奶牛（$1 \leq r_i \leq 1,000,000$）。

为了有序地把奶牛赶进牛棚，他计划解锁 $k$ 扇外部门（$1 \leq k \leq 7$），使奶牛只能从这些门进入。每头奶牛进入后会沿顺时针方向穿过房间，直到到达合适的目的房间。Farmer John 想要选择解锁哪些外部门，使得奶牛进入牛棚后需要行走的总距离最小（奶牛可以在牛棚外的 $k$ 扇已解锁门前以任意方式排队；这不计入所讨论的总距离）。

请计算：如果他选择最优的 $k$ 扇门来解锁，奶牛需要行走的最小总距离是多少。

输入格式

第一行包含 $n$ 和 $k$。 接下来的 $n$ 行每行包含一个数，依次为 $r_1 \ldots r_n$。

输出格式

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

6 2
2
5
4
2
6
2

14

提示

Farmer John 可以解锁第 2 个和第 5 个门。11 头奶牛从第 2 个门进入，总共行走距离为 8，前往房间 2、3 和 4。10 头奶牛从第 5 个门进入，总共行走距离为 6，前往房间 5、6 和 1。

题目致谢：Brian Dean

标签: USACO|2016|Gold

来源

USACO|2016|Gold