题目链接

https://www.luogu.com.cn/problem/P1880

普通dp题解链接

https://blog.nowcoder.net/n/420fe9ffda304281ad58f7abc03fb107

四边形不等式优化

很显然，直接区间dp板子搞上的时间复杂度为n^3，n到1000就TLE了。
通过四边形不等式优化可以将时间复杂度降至n^2。
我不会证明，能背过结论就不错了，WTCL。
结论：记住吧我还是
求最小值可以使用四边形不等式优化，但是求最大值不行，因为求最大值不满足某些条件。
但是最大值的最优决策要么是k=i，要么是k=j-1，所以一个max(dp[i][i]+dp[i+1][j],dp[i][j-1]+dp[j][j])+sum[j]-sum[i-1]就求出了最大值（并非最终结果的最大值）。
当问题是最小值时，我们就可以用四边形不等式优化了。此时，对于dp[i][j]，我们只需要在区间[ best[i][j−1],best[i+1][j] ]枚举k即可，时间复杂度为O(n^2)。
至于如何刷新best的值，看代码吧（挺简单的），我还是不知道咋证明。

参考大佬的题解链接

大佬本题题解
关于四边形优化的证明挺多的，但是我都没看懂，就上面这个大佬的结论比较清楚。
这还有个板子，不过讲的不是很清楚，理解了之后再看比较好

AC代码

#include<bits/stdc++.h>
#define sc(x) scanf("%d",&x)
#define pr(x) printf("%d",x)
#define ll long long
using namespace std;
const int N=300;
const int inf=0x3f3f3f3f;
int n,sum[N],mn[N][N],mx[N][N],a[N],best[N][N];
int maxx,minn=inf;
int main(){
    sc(n);
    for(int i=1;i<=n;i++) sc(a[i]),sum[i]=sum[i-1]+a[i],best[i][i]=i;
    for(int i=1;i<=n;i++) sum[i+n]=sum[i+n-1]+a[i],best[i+n][i+n]=i+n;//best要初始化，就是将best[i][i]初始化为i

    for(int len=2;len<=n;len++)
        for(int L=1;L<n+n;L++){
            int R=L+len-1;
            if(R>n+n) break;

            mn[L][R]=inf;
            for(int M=best[L][R-1];M<=best[L+1][R];M++){
                if(mn[L][R]>mn[L][M]+mn[M+1][R]+sum[R]-sum[L-1]){
                    best[L][R]=M;//刷新最小值的同时刷新best
                    mn[L][R]=mn[L][M]+mn[M+1][R]+sum[R]-sum[L-1];
                }    
            }

            mx[L][R]=max(mx[L][L]+mx[L+1][R],mx[L][R-1]+mx[R][R])+sum[R]-sum[L-1];
        }

    for(int i=1;i<=n;i++){
        maxx=max(maxx,mx[i][i+n-1]);
        minn=min(minn,mn[i][i+n-1]);
    }

    pr(minn);printf("\n");pr(maxx);
}