#include<bits/stdc++.h>
using namespace std;
int a[210], sa[210], f[210][210];
int main()
{
    int n;scanf("%d", &n);
    for(int i=1;i<=n;i++)scanf("%d", &a[i]);
    
    int ans=0x1fffffff;//5亿 
    for(int t=1;t<n;t++)//枚举交换的情况 
    {
        swap(a[t], a[t+1]);
        sa[0]=0;for(int i=1;i<=n;i++) sa[i]=sa[i-1]+a[i];
        swap(a[t], a[t+1]);//记得恢复原样 
        memset(f, 63, sizeof(f));
        for(int i=1;i<=n;i++)f[i][i]=0;//规模为1的状态 
        for(int L=2;L<=n;L++)//枚举规模为L的所有状态，最后完成规模为n的状态 
            for(int st=1;st<=n-L+1;st++)
            {
                int ed=st+L-1;
                for(int k=st;k<ed;k++)
                {
                    f[st][ed]=min(f[st][ed], f[st][k]+f[k+1][ed]+sa[ed]-sa[st-1]);
                }
            }
        ans=min(ans, f[1][n]);
    }
    printf("%d\n", ans);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int a[210],sa[210],f[210][210];
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    
    int ans=0x1fffffff;//5亿 
    for(int t=1;t<n;t++)//枚举交换的情况 
    {
        swap(a[t],a[t+1]);
        sa[0]=0;for(int i=1;i<=n;i++) sa[i]=sa[i-1]+a[i];
        swap(a[t],a[t+1]);//记得恢复原样 
        memset(f,63,sizeof(f));
        for(int i=1;i<=n;i++)f[i][i]=0;//规模为1的状态 
        for(int L=2;L<=n;L++)//枚举规模为L的所有状态，最后完成规模为n的状态 
            for(int st=1;st<=n-L+1;st++)
            {
                int ed=st+L-1;
                for(int k=st;k<ed;k++)
                {
                    f[st][ed]=min(f[st][ed],f[st][k]+f[k+1][ed]+sa[ed]-sa[st-1]);
                }
            }
        ans=min(ans,f[1][n]);
    }
    printf("%d\n",ans);
    return 0;
}

<br />

<br />