[NOI1995]石子合并 四边形不等式优化

链接

https://www.luogu.org/problemnew/show/P1880

思路

总之就是很牛逼的四边形不等式优化
复杂度\(O(n^2)\)

代码

#include <iostream>
#include <cstdio>
#include <cstring>
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;
}