DP/四边形不等式
这题跟石子合并有点像……
dp[i][j]为将第 i 个点开始的 j 个点合并的最小代价。
易知有 dp[i][j]=min{dp[i][j] , dp[i][k-i+1]+dp[k+1][j-(k-i+1)]+w(i,k,j)}
(这个地方一开始写错了……)
即，将一棵树从k处断开成(i,k)和(k+1,i+j-1)两棵树，再加上将两棵树连起来的两条树枝的长度w(i,k,j)
其中，$ w(i,k,j)=x[k+1]-x[i]+y[k]-y[i+j-1] $
那么根据四边形不等式易知 $s[i][j-1] \leq k \leq s[i+1][j-1] $
如果觉得上面那种不好懂，那我们来看个好懂的：
dp[i][j]表示将第 i 个点到第 j 个点合并的最小代价。
易知有 dp[i][j]=min{ dp[i][j],dp[i][k]+dp[k+1][j]+w(i,k,j) }
即，将一棵树从k处断开成(i,k)和(k+1,j) 两棵树，再加上将两棵树连起来的两条树枝的长度w(i,k,j)
w(i,k,j)的定义与上同
那么根据四边形不等式易知 $s[i][j-1] \leq k \leq s[i+1][j] $
其实，两种表示方法是一样的，递推时都按照区间长度为阶段进行递推（想一想，第二种中 (i,j-1) 和 (i+1,j) 的长度是不是 都是(i,j)的长度-1？）
只是第二种写法的方程看上去好看，也好写……sigh那我写第一种干嘛T_T算了不改了
反正基本就是石子合并的原题啦~除了w函数的定义不同……
//HDOJ 3516
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
#define CC(a,b) memset(a,b,sizeof(a))
using namespace std;
int getint(){
int v=,sign=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') sign=-; ch=getchar();}
while(isdigit(ch)) {v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=,INF=~0u>>;
const double eps=1e-;
/*******************template********************/
//#define debug
int x[N],y[N],dp[N][N],s[N][N];
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
#endif
int n;
while(scanf("%d",&n)!=EOF){
F(i,,n) x[i]=getint(),y[i]=getint();
F(i,,n){
dp[i][]=;
s[i][]=i;
}
F(i,,n-){
dp[i][]=x[i+]-x[i]+y[i]-y[i+];
s[i][]=i;
}
#ifdef debug
F(i,,n-) printf("%d ",dp[i][]);
printf("\n");
#endif
F(j,,n)
F(i,,n-j+){
dp[i][j]=INF;
F(k,s[i][j-],s[i+][j-]){
int tmp=y[k]-y[i+j-]+x[k+]-x[i]+dp[i][k-i+]+dp[k+][j-(k-i+)];
#ifdef debug
printf("i=%d k=%d j=%d\n",i,k,j);
printf("dp[i][k-i+1]=%d dp[k+1][j-k]=%d\n",dp[i][k-i+],dp[k+][j-k]);
#endif
if (tmp<dp[i][j]){
s[i][j]=k;
dp[i][j]=tmp;
}
}
}
#ifdef debug
F(j,,n){
F(i,,n) printf("%d ",dp[i][j]);
printf("\n");
}
F(j,,n){
F(i,,n) printf("%d ",s[i][j]);
printf("\n");
}
#endif
printf("%d\n",dp[][n]);
}
return ;
}
(156MS 9076K)