DP/四边形不等式
裸题环形石子合并……
拆环为链即可
//HDOJ 3506
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
#define CC(a,b) memset(a,b,sizeof(a))
using namespace std;
int getint(){
int v=,sign=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') sign=-; ch=getchar();}
while(isdigit(ch)) {v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=;
const int INF=;
const double eps=1e-;
/*******************template********************/
int s[N][N],a[N];
int dp[N][N];
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
#endif
int n;
while(scanf("%d",&n)!=EOF && n){
CC(a,);CC(s,);
F(i,,n) a[i+n]=a[i]=getint();
F(i,,n<<) a[i]+=a[i-];
F(i,,n*-){
dp[i][i+]=a[i+]-a[i-];
s[i][i+]=i;
}
F(len,,n)
F(i,,n*-len+){
int j=i+len-;
dp[i][j]=INF;
F(k,s[i][j-],s[i+][j]){
int tmp=dp[i][k]+dp[k+][j]+a[j]-a[i-];
if (tmp<dp[i][j]){
dp[i][j]=tmp;
s[i][j]=k;
}
}
}
int ans=INF;
F(i,,n) ans=min(ans,dp[i][i+n-]);
printf("%d\n",ans);
}
return ;
}