题目描述

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

数据范围

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;
}

分享至ヾ(≧∇≦*)ゝ:

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *