NOIp模拟 二叉搜索树

船送门 用四边形不等式优化的区间$DP$。 至于四边形不等式，特征一般都很明显，而且这东西很偏。记结论，然后给决策点打表找规律就行了吧。 由决策点的单调性把$O(n^3)$优化成$O(n^2)$。

#include<bits/stdc++.h> #define ll long long #define re register #define cs const cs int N=5e3+10; cs ll oo=1e18; namespace IO{ cs int Rlen=1<<22|1; char buf[Rlen],*p1,*p2; inline char gc(){return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;} template<typename T> inline T get(){ char ch=gc();T x=0; while(!isdigit(ch)) ch=gc(); while(isdigit(ch)) x=(x+(x<<2)<<1)+(ch^48),ch=gc(); return x; } inline int gi(){return get<int>();} inline ll gl(){return get<ll>();} } using IO::gi; using IO::gl; int n;ll val[N][N],sum[N],pos[N][N]; int i,L,R,len,mid; int main(){ // freopen("tree.in","r",stdin); // freopen("tree.out","w",stdout); n=gi(); for(i=1;i<=n;++i) pos[i][i]=i,val[i][i]=gl(),sum[i]=sum[i-1]+val[i][i]; for(len=2;len<=n;++len){ for(L=1;(R=L+len-1)<=n;++L){ val[L][R]=oo; for(mid=pos[L][R-1];mid<=pos[L+1][R];++mid) if(val[L][R]>val[L][mid-1]+val[mid+1][R]) val[L][R]=val[L][mid-1]+val[mid+1][R],pos[L][R]=mid; val[L][R]+=sum[R]-sum[L-1]; } }printf("%lld\n",val[1][n]); }