Vijos 1014 旅行商简化版 解题报告

CLRS上经典的双调欧几里德旅行商问题模型。先对所有点按x坐标排序，规定第i个点为x坐标第i小的点。显然题目要求的双调路径可以看作两个人同时从起点走到终点且所经过的点的x坐标严格递增。用f[i,j]表示第一个人走到第i个点，第二个人走到第j个点的双调路径的长度最小值。显然f[i,j]和f[j,i]是相等的，因此为了处理方便规定i>=j。又由于显然所求双调路径只有起点和终点会出现i=j，所以DP过程中保证i>j，f[n,n]的情况最后特殊处理即可。此外f[i,1]的情况也需要预处理一下。

又因为题目要求这一双调路径必须是哈密顿回路，即每一个点都经过且仅经过一次，所以可以得到状态转移方程：

• f[i,i+1]=min(f[i,i+1],f[i,j]+dist[j,i+1])(1<=i<n,1<=j<i);
• f[i+1,j]=min(f[i+1,j],f[i,j]+dist[i,i+1])(1<=i<n,1<=j<i);

注意方程的状态转移过程，显然要到达第i+1个点必须先到达第i个点。f[n,n]=min(f[n,n],f[n,i]+dist[i,n])(1<=i<n)。

R1074322 Accepted 100 From IwfWcf P1014    FPC Vivid Puppy 2008-11-23 10:01:26