P1880 [NOI1995]石子合并[区间dp+四边形不等式优化]

P1880 [NOI1995]石子合并

---

丢个地址就跑（关于四边形不等式复杂度是n方的证明）

嗯所以这题利用决策的单调性来减少k断点的枚举次数。具体看lyd书。这部分很生疏，但是我还是选择先不管了。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 typedef double db;

 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,:;}

 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,:;}

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 const int N=+,INF=0x3f3f3f3f;

 int p[N][N],Fmin[N][N],Fmax[N][N],sum[N],a[N];

 int n;

 int main(){//freopen("tmp.in","r",stdin);freopen("tmp.out","w",stdout);

     read(n);

     for(register int i=;i<=n;++i)a[i+n]=read(a[i]);

     for(register int i=;i<(n<<);++i)sum[i]=sum[i-]+a[i],p[i][i]=i;

     for(register int i=(n<<)-;i;--i){

         for(register int j=i+;j<(n<<);++j){

             Fmax[i][j]=_max(Fmax[i+][j],Fmax[i][j-])+sum[j]-sum[i-];Fmin[i][j]=INF;

             for(register int k=p[i][j-];k<=p[i+][j];++k)

                 if(MIN(Fmin[i][j],Fmin[i][k]+Fmin[k+][j]+sum[j]-sum[i-]))p[i][j]=k;

             if(!(Fmin[i][j]^INF))Fmin[i][j]=;

         }

     }

     Fmin[][]=INF;

     for(register int i=;i<=n;++i)MIN(Fmin[][],Fmin[i][i+n-]),MAX(Fmax[][],Fmax[i][i+n-]);

     printf("%d\n%d\n",Fmin[][],Fmax[][]);

     return ;

 }