题目描述

Being a fan of contemporary architecture, Farmer John has built a new barn in the shape of a perfect circle. Inside, the barn consists of a ring of n rooms, numbered clockwise from 1…n around the perimeter of the barn (3≤n≤1,000). Each room has doors to its two neighboring rooms, and also a door opening to the exterior of the barn.
Farmer John wants exactly ri cows to end up in each room i (1≤ri≤100). To herd the cows into the barn in an orderly fashion, he plans to unlock the exterior door of a single room, allowing the cows to enter through that door. Each cow then walks clockwise through the rooms until she reaches a suitable destination. Farmer John wants to unlock the exterior door that will cause his cows to collectively walk a minimum total amount of distance. Please determine the minimum total distance his cows will need to walk, if he chooses the best such door to unlock. The distance walked by a single cow is the number of interior doors through which she passes.

输入描述:

The first line of input contains n. Each of the remaining n lines contain r1…rn.

输出描述:

Please write out the minimum total amount of distance the cows collectively need to travel.

示例1

输入
5
4
7
8
6
4
输出
48
说明
In this example, the best solution is to let the cows enter through the door of the room that requires 7 cows.

解答

暴力枚举每个点的值，最后求一个最小的

每次转移的时候，可以通过上一个转移求得

这样复杂度就是 

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<set>
#include<queue>
using namespace std;
#define ll long long
int a[1005];
int main()
{
    std::ios::sync_with_stdio(false);
    int n,tol=0,cnt=0,ans,i;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
        tol+=a[i];
    }
    a[0]=a[n];
    a[n+1]=a[1];
    for(i=2;i<=n;i++){
        cnt+=(i-1)*a[i];
    }
    ans=cnt;
    for(i=2;i<=n;i++){
        cnt=cnt-(tol-a[i]-a[i-1])-a[i]+(n-1)*a[i-1];
        ans=min(ans,cnt);
    }
    printf("%d\n",ans);
     
 
 return 0;
}

来源：甦萌