最短距离
这 道 题 我 完 全 想 偏 了
给定一个二叉树的中序遍历，要求所有可能的二叉树中所有子节点到根节点的最短距离。
非常菜的我看到这道题首先就想到要把所有的树先造出来...可是发现并不能做，此时考试都快完了...
在快结束的时候想到了分治，将整棵树无限拆开取min(我也不知道可不可做希望各位dalao给些意见)。
今天琢磨了好久也没琢磨得很明白...于是咨询了想出正解的xk，感觉自己对DP的理解差了太多...
设f[i][j]为i-j区间的最小值，可以考虑到每一个点对答案都会有一个贡献，因此我们把i-j的这一段视作一颗子树，计算该子树可以带来的贡献，得到转移方程为：
f[i][j]=min(f[i][j],f[i][k-1]+f[k+1][j]+a[k]*(j-i+1));
方程蛮好想的应该不用我解释了
贴代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=4e2+5,inf=0x3f3f3f3f;
int n;
long long ans=inf,a[maxn],f[maxn][maxn];
int main(){
memset(f,0x3f,sizeof f);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=1;i<=n+1;i++) f[i][i]=a[i],f[i][i-1]=0;
for(int t=2;t<n;t++){
for(int i=1;i+t-1<=n;i++){
int j=i+t-1;
for(int k=i;k<=j;k++){
f[i][j]=min(f[i][j],f[i][k-1]+f[k+1][j]+a[k]*(j-i+1));
}
}
}
for(int i=1;i<=n;i++) ans=min(ans,f[1][i-1]+f[i+1][n]);
printf("%lld",ans);
return 0;
}考虑一下初始化，f[i][i]自然就是该点的权值，f[i][i-1]这个东西在状态转移的时候并没有用(因为无论如何i都比j小),这个东西是在最后ans处要用。
前面已经说过f[i][j]是子树而非一整棵树，所以最终的答案需要枚举一下根节点并取一个min。而此时如果没有初始化f[i][i-1]的话,i-1和i+1很有可能越界导致答案最终变成inf。因此越界部分初始化成0。
至此这道题就说的差不多了。
这个题也要用long long不然会WA一个点不要问我怎么知道的