P6958: 圆形谷仓
传统题
1.000s
时间限制
256MB
内存限制
0 提交
0 解决
【题目描述】
【题目描述】
作为当代建筑的爱好者，农夫约翰建造了一个完美的圆形新谷仓。在谷仓内部，由n个房间组成的圈，围绕谷仓的周长顺时针从1…n开始编号(3≤n≤1000)。每个房间都有一扇通向相邻的两个房间的门，还有一扇门通向谷仓的外部。
农夫约翰有n头牛，他希望谷仓里的每个房间都有一头牛。然而，奶牛有点困惑，在任意的门前排队，可能有多头牛在同一扇门前排队。准确地说，奶牛排在房间的门外，因此∑ci=n。
为了管理牛群的放牧过程，使每个房间都有一头牛，农民约翰想使用以下方法:每头牛从它最初排队的那扇门进入，然后顺时针穿过房间，直到到达合适的目的地。假设一头牛走过d扇门需要消耗d2能量，请确定分配奶牛所需的最小能量，使每个房间都有一头奶牛。
【输入格式】(cbarn.in):
第一行输入一个整数n，其余n行中每一行包含一个整数c1…cn。
【输出格式】(cbarn.out)
请写出奶牛消耗的最小能量。
【样例输入】:
10
1
0
0
2
0
0
1
2
2
2
【样例输出】:
33