【HDU】3516 Tree Construction

http://acm.hdu.edu.cn/showproblem.php?pid=3516

题意：平面n个点且满足xi<xj, yi>yj, i<j。xi，yi均为整数。求一棵树边只能向上和向右延展的经过所有点的最小长度。（n<=1000, 0<=xi, yi<=10000）

#include <cstdio>
using namespace std;
const int N=1005, oo=~0u>>1;
int d[N][N], x[N], y[N], n, s[N][N];
int main() {
	while(~scanf("%d", &n)) {
		for(int i=1; i<=n; ++i) scanf("%d%d", &x[i], &y[i]);
		for(int i=1; i<n; ++i) d[i][i+1]=y[i]-y[i+1]+x[i+1]-x[i], s[i][i+1]=i+1;
		for(int len=3; len<=n; ++len)
			for(int i=1; i<=n-len+1; ++i) {
				int j=i+len-1, l=s[i][j-1], r=s[i+1][j], &now=d[i][j], &pos=s[i][j];
				now=oo;
				for(int k=l; k<=r; ++k) {
					int t=d[i][k-1]+d[k][j]+y[k-1]-y[j]+x[k]-x[i];
					if(now>=t) {
						now=t;
						pos=k;
					}
				}
			}
		printf("%d
", d[1][n]);
	}
	return 0;
}

　　

一开始乱想= =乱搞无果= =b，于是妈呀看了题解 = =

妈呀我没想到.....d(i, j)表示i～j个点的最小代价，由于点都满足题目所给的条件，对于两棵i~k-1, k~j的树连接起来显然代价为y[k-1]-y[j]+x[k]-x[i]

设$w(i, j, k)=y[k-1]-y[j]+x[k]-x[i]$，那么得到：

$$d(i, j)=min { d(i, k-1)+d(k, j)+w(i, j, k) }, i<j$$

我一开始看到$w$是三元的= =便又手推了一下四边形不等式的证明= =发现这竟然和$k$无关！即如果四边形不等式满足$w(i, j, k)+w(i', j', k) le w(i', j, k)+w(i, j', k)$，那么和原来的一模一样！原因在哪？因为我是一个sb= =关于$w$的不等式左右加上两个$y[k-1]+x[k]$是可以约掉的我还傻x的重新证明了一下！

那么本题直接把状态变为$w(i, j)$先不管$k$了= =

我们先来证明$w$的区间单调性，很显然吧...题目已经满足= =

然后来证明$w$的四边形不等式....首先我们要一个容易证明不等式成立的式子= =

首先四边形不等式变形为

$$w(i, j')-w(i, j) ge w(i', j')-w(i', j)$$

发现当$j$不变时（即固定），那么我们只需要判断$w(i, j')-w(i, j)$的$i$如果增大值是变大还是变小即可，如果是变小（递减）显然满足四边形不等式（因为$i' ge i$）。

所以得到一个定理：如果$w(i, j)$满足四边形不等式，则我们只需要判断：当j不变时，$w(i, j+1)-w(i, j)$是否单调递减即可。（j同理，咦j要不要一起证啊？）

那么本题由于$w(i, j+1)-w(i, j) = y[j]-y[j+1]$与$i$无关所以满足条件...

那么水题啦= =