链接

思路

总之就是很牛逼的四边形不等式优化

复杂度\(O(n^2)\)

代码

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int N=207;int read() {    int x=0,f=1;char s=getchar();    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';    return x*f;}int n,a[N],sum[N],f[2][N][N],g[N][N];inline int max(int a,int b) {return a>b?a:b;}inline int min(int a,int b) {return a>b?b:a;}int main() {    n=read();    for(int i=1;i<=n;++i) a[i+n]=a[i]=read();    for(int i=1;i<=n+n;++i) sum[i]=sum[i-1]+a[i];    memset(f[0],0x3f,sizeof(f[0]));    for(int i=1;i<=n+n;++i) f[0][i][i]=f[1][i][i]=0,g[i][i]=i;     for(int len=2;len<=n;++len) {        for(int i=1;i<=n+n;++i) {            int j=i+len-1;            if(j>n+n) continue;            f[1][i][j]=max(f[1][i][j-1],f[1][i+1][j])+sum[j]-sum[i-1];            for(int k=g[i][j-1];k<=g[i+1][j];++k) {                if(f[0][i][j]>f[0][i][k]+f[0][k+1][j]+sum[j]-sum[i-1]) {                    f[0][i][j]=f[0][i][k]+f[0][k+1][j]+sum[j]-sum[i-1];                    g[i][j]=k;                  }            }        }    }    int ans[2]={0x3f3f3f3f,-0x3f3f3f3f};    for(int i=1;i<=n;++i) {        ans[0]=min(ans[0],f[0][i][i+n-1]);        ans[1]=max(ans[1],f[1][i][i+n-1]);      }    printf("%d\n%d\n",ans[0],ans[1]);    return 0;}