题目描述

给你平面上三行的一些点，求一条经过所有点的最短回路。

数据范围

y 坐标小于等于 300，x 坐标小于等于 3000，每一行的点数小于等于 1300.

题目分析

虽然给的 solution 写的挺清晰的，但是我还是没看懂…… 然后打开标程，发现是 pascal 的…… 忽然想到以后的学弟学妹们也考这道题，也改这道题的时候，若是也没看懂 solution，就可以来看看这篇 blog ，然后感慨：虽然这个学姐因为太蒻滚粗辣但是博客写得还是不错的

以下 $(i,j)$表示第 i 行第 j 个点。
首先，如果没有这恼人的第二行，那么很简单，就直接从 $(1,1)$走到 $(1,n_1)$再走到 $(3,n_3)$再走到 $(3,1)$再走到 $(1,1)$就可以辣！这样一条路径，称作原路径。
那么我们一定是在这样一条路径的两个点之间突然 “跳” 到第二行去走一走然后回来。这种状态比较清晰，考虑动态规划。

令 L(i) 表示将 $(2,1)$到 $(2,i)$这样一段放在原路径左边的最小增量，R(i) 表示将 $(2,i)$到 $(i+1,n_2)$这样一段放在原路径右边的最小增量，M(i,j) 表示在原路径上面或下面走的时候突然抽风滚到第二行来走 i 到 j 这一段后回去的最小增量。
然后令 f(i) 表示第 2 行的前 i 个点已经被走过的时候的最小答案增量。
脑补出转移：f(i)=min(L(i),f(j-1)+M(j,i))。
那么 ans=min(f(i)+R(i+1))+原路径长度
现在我们考虑如何计算 L(i),R(i) 和 M(i)。

对于 L(i), 显然只有两种转移，即 L(i)=min(dis((1,1),(2,1))+dis((2,1),(2,i))+dis((2,i),(3,1)),dis((3,1),(2,1))+dis((2,1),(2,i))+dis((2,i),(1,1)))-dis((1,1),(3,1))
之所以最后要减，是因为我们要除去原路径的贡献，这样才能够算增量。
而 R(i) 也类似。

那么按照相似的思路，暂时只考虑从第一行抽风走到第二行（从第三行走也类似），则 M(i,j)=min(dis((1,k),(2,i))+dis((2,i),(2,j))+dis((2,j),(1,k+1))-dis((1,k),(1,k+1)))
可是这是一个 $O(n^3)$的转移！怎么办怎么办怎么办……
要把 $O(n^3)$优化到 $O(n^2)$，你是不是想起了什么……
四边形不等式！
猜测：若让 f(i,j) 取到最优解的 k 记做 g(i,j), 则 $g(i,j-1) \leq g(i,j) \leq g(i+1,j)$
严谨的证明我也不会（有请 boshi 同学），不过如果你在纸上画图搞一搞的话，一定会有感觉，偏左的区间，取的 k 值也应该偏左。偏右的区间，取的 k 值也应该偏右。
由此，这题得到了解决。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef double db;
const int N=1305;
const db inf=1e16;
int n[3];db y[3],ans;
db x[3][N],g0[N][N],g2[N][N],M[N][N],f[N];

db dis(db X1,db Y1,db X2,db Y2)
  {return sqrt((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2));}
db walk(int i,int j,int a,int b,int c,int d) {
    db re=dis(x[1][i],y[1],x[a][b],y[a]);
    re+=dis(x[c][d],y[c],x[1][j],y[1]);
    re-=dis(x[a][b],y[a],x[c][d],y[c]);
    return re;
}

void work1() {
    for(RI i=n[1];i>=1;--i) {
        for(RI j=i;j<=n[1];++j) {
            if(i==j) {
                g0[i][j-1]=1,g0[i+1][j]=n[0]-1;
                g2[i][j-1]=1,g2[i+1][j]=n[2]-1;
            }
            db mxx=inf;
            for(RI k=g0[i][j-1];k<=g0[i+1][j];++k) {
                db kl=walk(i,j,0,k,0,k+1);
                if(kl<mxx) mxx=kl,g0[i][j]=k;
            }
            M[i][j]=mxx,mxx=inf;
            for(RI k=g2[i][j-1];k<=g2[i+1][j];++k) {
                db kl=walk(i,j,2,k,2,k+1);
                if(kl<mxx) mxx=kl,g2[i][j]=k;
            }
            if(mxx<M[i][j]) M[i][j]=mxx;
            M[i][j]+=x[1][j]-x[1][i];
        }
    }
}
void work2() {
    for(RI i=1;i<=n[1];++i) {
        db L=min(walk(1,i,0,1,2,1),walk(1,i,2,1,0,1));
        f[i]=L+x[1][i]-x[1][1];
        for(int j=1;j<=i;++j) f[i]=min(f[i],f[j-1]+M[j][i]);
    }
    ans=f[n[1]];
    for(RI i=n[1]-1;i>=1;--i) {
        db R=min(walk(i+1,n[1],0,n[0],2,n[2]),walk(i+1,n[1],2,n[2],0,n[0]));
        ans=min(ans,f[i]+R+x[1][n[1]]-x[1][i+1]);
    }
    ans+=x[0][n[0]]-x[0][1]+x[2][n[2]]-x[2][1];
    ans+=dis(x[0][1],y[0],x[2][1],y[2]);
    ans+=dis(x[0][n[0]],y[0],x[2][n[2]],y[2]);
}
int main()
{
    freopen("dna.in","r",stdin);
    freopen("dna.out","w",stdout);
    scanf("%d%d%d",&n[0],&n[1],&n[2]);
    scanf("%lf%lf%lf",&y[0],&y[1],&y[2]);
    for(RI i=0;i<=2;++i)
        for(RI j=1;j<=n[i];++j) scanf("%lf",&x[i][j]);
    work1(),work2();
    printf("%.2lf\n",ans);
    return 0;
}