[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\)。