题目大意：平面上有n个点，构成一个单调递减的序列。即对于任意的i<j,有xi<xj,yi>yj。现在要用一棵树连接这n个点。树边为有向边，只能向右或向上。求最小的权值。
分析：本题其实是式子合并的变形。
f[i][j]=f[i][k]+f[k+1][j]+y[k]-y[j]+x[k+1]-x[i]
其中s[i][j-1]<=s[i][j]<=s[i+1][j]
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define MAXN 1005
int x[MAXN],y[MAXN],f[MAXN][MAXN],s[MAXN][MAXN];
int main()
{
int n;
while(scanf("%d",&n)!=-)
{
for(int i=;i<=n;i++)
scanf("%d%d",&x[i],&y[i]);
memset(f,0x3f,sizeof f);
for(int i=;i<=n;i++)
f[i][i]=;
for(int i=;i<=n;i++){s[i][i]=i;}
for(int i=n-;i>=;i--)
for(int j=i+;j<=n;j++)
{
for(int k=s[i][j-];k<=s[i+][j];k++)
if(f[i][j]>f[i][k]+f[k+][j]+y[k]-y[j]+x[k+]-x[i])
{f[i][j]=f[i][k]+f[k+][j]+y[k]-y[j]+x[k+]-x[i];
s[i][j]=k;
}
}
printf("%d\n",f[][n]);
}
}