HDU 3516 Tree Construction

好久没更博客了

CSP 2019 凉凉。。

---

这个题看起来就很像区间dp，可以写出

$dp[i][j] = max\{dp[i][k]+dp[k+1][r]+x_{k+1}-x_i+y_k-y_r\}$

就是考虑$[i,j]$这个区间，其中从$[l,k] , [k + 1 , r]$这两个区间都被构造好了树，然后树的构造大概是

打表发现它满足四边形不等式。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
#define MAXN 1016
int n;
int x[MAXN] , y[MAXN];
int dp[MAXN][MAXN] , mn[MAXN][MAXN];
int main() {
	while( cin >> n ) {
		for( int i = 1 ; i <= n ; ++ i ) scanf("%d%d",&x[i],&y[i]);
		memset( dp , 0x3f , sizeof dp );
		for( int i = 1 ; i <= n ; ++ i ) dp[i][i] = 0 , mn[i][i] = i;
		for( int len = 2 ; len <= n ; ++ len ) {
			for( int i = 1 ; i + len - 1 <= n ; ++ i ) {
				int j = i + len - 1;
				for( int k = mn[i][j - 1] ; k <= mn[i + 1][j] ; ++ k ) {
					int t = dp[i][k] + dp[k + 1][j] + x[k+1] - x[i] + y[k] - y[j];
					if( t < dp[i][j] ) 
						mn[i][j] = k , dp[i][j] = t;
				}
			}
		}
		cout << dp[1][n] << endl;
	}
}