相信大家都会$O(n^3)$的dp做法了，这里就不在赘述了
可$n\leq 5000$啊!
成功引出DP四边形不等式优化
讲解
对于本题，可以先用大样例本地跑$O(n^3)$测试cost是否为凸、dp是否为凸、决策是否单调。
answer：是的
所以$[i,j]$的分割点一定在$[i,j-1]$的分割点与$[i+1,j]$的分割点之间
于是就优化掉一维$O(n)$的决策，共$O(n^2)$
CODE:

//https://www.acwing.com/problem/content/description/2892/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define FOR(i,j,k) for(register int i=j;(j<k)?(i<=k):(i>=k);i+=(j<k)?1:(-1))
#define IO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define N 5050 

int pre[N];//前缀和 
int s[N][N];//决策（分割点）
int dp[N][N];//ans 
int a[N],r,n,ans;
signed main(){
    IO;
    memset(dp,inf,sizeof dp);
    cin>>n;
    FOR(i,1,n)cin>>a[i];
    FOR(i,1,n)pre[i]=pre[i-1]+a[i];
    FOR(i,1,n)s[i][i]=i;
    FOR(i,1,n)dp[i][i]=0;
    FOR(i,2,n){
        FOR(l,1,n-i+1){
            r=l+i-1;
            FOR(k,s[l][r-1],s[l+1][r]){
                ans=dp[l][k]+dp[k+1][r];
                if(ans<dp[l][r]){
                    dp[l][r]=ans;
                    s[l][r]=k;
                }
            }
            dp[l][r]+=pre[r]-pre[l-1];
//          cout<<l<<" "<<r<<" "<<s[l][r]<<" "<<dp[l][r]<<endl;
        }
    }
    cout<<dp[1][n];
    return 0;
}