经过昨天一晚上的冥思苦想以及 对四边形不等式的研究，我终于将T2的正解打了出来。
先看题： 就是保证一棵树的中序遍历不变，让你构造一棵树，满足题意。
这道题可以用区间DP，令 f i , j f_{i,j} fi,j表示只考虑节点[ i , j ]的答案。 在[i,j]区间中枚举决策点（根节点）k，则有 f i , j = m i n ( f i , k − 1 , f k + 1 , j ) + ∑ x = i j s u m [ x ] f_{i,j}=min(f_{i,k-1},f_{k+1,j})+\sum_{x=i}^jsum[x] fi,j=min(fi,k−1,fk+1,j)+∑x=ijsum[x], 其中sum[x]为节点[ i , j ]的权值之和，可以用预处理的 j 的前缀和减去 i 的前缀和得到。 这是O（n 2 ^2 2）的做法，可以得40分。
接下来我们就要用到四边形不等式优化（详情可在《算法竞赛进阶指南》上查找） 可以证明 f i , j f_{i,j} fi,j满足四边形不等式，则有k单调，所以我们只需在[ i ,j-1 ]与[ i+1 , j ]的决策点之间枚举即可。
下面贴代码：
#include<bits/stdc++.h> using namespace std; #define in read() int n,aa,p[5005][5005]; long long f[5005][5005],a[5005]; int in { int i=0;char ch=0; while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) {i=i*10+ch-'0';ch=getchar();} return i; } int main() { freopen("tree.in","r",stdin); freopen("tree.out","w",stdout); n=in; for(int i=1;i<=n;i++) { aa=in; a[i]=a[i-1]+aa; } for(int l=n;l>=1;l--) for(int r=l;r<=n;r++) { f[l][r]=a[r]-a[l-1]; if(l==r) {p[l][r]=l;continue;} long long minn=1e15; for(int i=p[l][r-1];i<=p[l+1][r];i++) { if(f[l][i-1]+f[i+1][r]<minn) minn=f[l][i-1]+f[i+1][r],p[l][r]=i; } f[l][r]+=minn; } printf("%lld",f[1][n]); return 0; }