/ WHOJ / 题库 /

[USACO2016 Feb]Circular Barn / 圆形牛棚

[USACO2016 Feb]Circular Barn / 圆形牛棚

题目描述

农夫约翰建了一个新的圆形牛棚,棚内沿着圆周有隔开的 \(n\) 个小房间,将其按顺时针方向用数字 \(1…n\) 进行编号。其中每个小房间都有门通往棚外和其相邻的两个房间。现在农夫约翰想要把奶牛赶进牛棚,并在每个小房间都安置 \(r[i]\) 只奶牛 \((1≤r[i]≤100)\)。他计划只打开其中一个房间通往牛棚外部的门,让所有牛从这里进入,并让它们有序地沿顺时针方向穿过别的房间,直到它们到达合适的安置点。
农夫约翰希望选择的这一扇外门能令所有牛行走的距离总和最小。请算在此情况下的距离总和。(每头牛的行走距离用它所穿过的门的数量来表示)

格式

输入格式

输入的第一行包含 \(n\)。接下来的 \(n\) 行每行一个整数,表示 \(r[1]…r[n]\)。

输出格式

输出所有牛行走的最小距离总和。

样例1

样例输入1

5
4
7
8
6
4

样例输出1

48

样例解释

在这一题中,最佳的解决方案如下图:
说明

限制

\(100\%\) 的数据:\(3≤n≤1000\)。