Circular Barn

题目描述

作为当代建筑的爱好者，农夫约翰建造了一个全新的谷仓，其形状为一个完美的圆。谷仓内部由一个包含 $n$ 个房间的环组成，房间沿谷仓周边按顺时针方向编号为 $1 \ldots n$（$3 \leq n \leq 1000$）。每个房间都有通往相邻两个房间的门，并且还有一扇通往谷仓外部的门。 农夫约翰有 $n$ 头奶牛，他希望最终每个房间恰好有一头奶牛。然而，这些奶牛有些迷糊，会在各个门口随意排队，可能有多个奶牛排在同一个门口。具体地，有恰好 $c_i$ 头奶牛排在房间 $i$ 的门外，因此 $\sum c_i = n$。 为了管理赶牛过程，使得每个房间最终有一头奶牛，农夫约翰打算采用如下方法：每头奶牛从她最初排队的门进入，然后沿着房间顺时针行走，直到到达一个合适的目的地。已知奶牛穿过 $d$ 扇门会消耗 $d^2$ 的能量，请你计算为了把奶牛分配到各个房间并使每个房间恰好有一头奶牛所需消耗的最小总能量。

输入格式

第一行输入包含 $n$。 接下来的 $n$ 行每行包含 $c_1 \ldots c_n$。

输出格式

请输出奶牛消耗的最小总能量。

10
1
0
0
2
0
0
1
2
2
2

33

提示

题目来源：Brian Dean

标签: USACO|2016|Silver

来源

USACO|2016|Silver