#include <set> #include <map> #include <ctime> #include <queue> #include <cmath> #include <stack> #include <limits> #include <vector> #include <bitset> #include <string> #include <cstdio> #include <cstring> #include <fstream> #include <string.h> #include <iostream> #include <algorithm> #define LL long long #define Vi vector<int> #define Si set<int> #define readf freopen("input.txt","r",stdin) #define writef freopen("output.txt","w",stdout) #define FF(i,a) for(int i(0); i < (a); i++) #define FD(i,a) for(int i(a); i >= (1); i--) #define FOR(i,a,b) for(int i(a);i <= (b); i++) #define FOD(i,a,b) for(int i(a);i >= (b); i--) #define PD(a) printf("%d\n",a) #define SET(a,b) memset(a,b,sizeof(a)) #define SD(a) scanf("%d",&(a)) #define LN printf("\n") #define PS printf(" ") #define pb push_back #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const double pi = acos(-1.0); const int maxn = 301; const int INF = 99999999; const int dx[]={0,1,0,-1}; const int dy[]={1,0,-1,0}; using namespace std; int N,tmp; int sum[maxn],f[maxn][maxn]; int dp(int l,int r) { int i,ans,t; if (f[l][r]>=0) return f[l][r]; ans=0x7fffffff; FOR(i,l,r-1) { t=dp(l,i)+dp(i+1,r)+sum[r]-sum[l-1]; if (ans>t) ans=t; } f[l][r]=ans; return f[l][r]; } int main(){ SD(N); FOR(i,1,N){ SD(tmp); sum[i]=sum[i-1]+tmp; //printf("sum[%d]=%d\n",i,sum[i]); f[i][i]=0; //自己和自己合并当然合并值为0; } FOR(i,1,N) FOR(j,i+1,N) f[i][j]=-1; dp(1,N); printf("%d\n",f[1][N]); return 0; }