Discription

Far away from our world, there is a banana forest. And many lovely monkeys live there. One day, SDH(Song Da Hou), who is the king of banana forest, decides to hold a big party to celebrate Crazy Bananas Day. But the little monkeys don't know each other, so as the king, SDH must do something. 
Now there are n monkeys sitting in a circle, and each monkey has a making friends time. Also, each monkey has two neighbor. SDH wants to introduce them to each other, and the rules are: 
1.every time, he can only introduce one monkey and one of this monkey's neighbor. 
2.if he introduce A and B, then every monkey A already knows will know every monkey B already knows, and the total time for this introducing is the sum of the making friends time of all the monkeys A and B already knows; 
3.each little monkey knows himself; 
In order to begin the party and eat bananas as soon as possible, SDH want to know the mininal time he needs on introducing. 

8

5 2 4 7 6 1 3 9

105

发现这是一个四边形不等式的模板题

#include<bits/stdc++.h>

#define ll long long

#define maxn 2005

using namespace std;

int f[maxn][maxn],n,m,w[maxn];

int pos[maxn][maxn],ans,l,r;

int main(){

	while(scanf("%d",&n)==1){

		ans=1<<30;

		memset(f,0x3f,sizeof(f));

		for(int i=1;i<=n;i++){

			scanf("%d",w+i),w[i+n]=w[i];

			f[i][i]=f[i+n][i+n]=0;

			pos[i][i]=i,pos[i+n][i+n]=i+n;

		}

		m=n<<1;

		for(int i=1;i<=m;i++) w[i]+=w[i-1];

		for(int len=1;len<n;len++)

			for(int i=1,j;(j=i+len)<=m;i++){

				l=pos[i][j-1],r=pos[i+1][j];

				for(int u=l;u<=r;u++) if(f[i][u]+f[u+1][j]<f[i][j]){

					f[i][j]=f[i][u]+f[u+1][j];

					pos[i][j]=u;

				}

				f[i][j]+=w[j]-w[i-1];

			}

		for(int i=1;i<=n;i++) ans=min(ans,f[i][i+n-1]);

//		for(int i=1;i<m;i++)

//		    for(int j=i;j<=m;j++) printf("%d %d:%d, %d \n",i,j,f[i][j],pos[i][j]);

		printf("%d\n",ans);

	}

	return 0;

}