P1354题解

· · 个人记录

学完基础搜索就能A一道紫题！（一道缝缝补补过的题）

题目传送门

另外我发现洛谷的数据太水了，提交下面的试试，只是加了多组数据。

POJ-1556

题目分析：

第一眼可能觉得题目很简单，但细想发现难点在于：

不知道从i墙哪里到j墙哪里最短，每个空可以无限多个点，以及不能只看两墙最短，要考虑墙与墙的连接，我觉得这就是卡精度。

方法呢？

直接dfs从后向前跑（主要是我只想到这个），dfs（n，to）表示从开始到第n堵墙to的y坐标的最小距离。那么答案就是dfs（n+1，5）（最后一个墙加上），具体的暴力如下：

const int N=20;
const double eps=1e-3,inf=100000;
//inf 最大距离，其实我觉得开100就好了，10*10的面积嘛，但这样保险
\\eps 精度 1e-3:10的负3次方,也就是0.001
struct Node{
    double x,
        y[5];
}w[N];//存墙
double count(int n,double i,double to){
//n 第i堵墙，
//i 第n-1堵墙的y坐标
//to 必须到n堵墙的y坐标
//作用：计算相邻2堵墙距离
    return sqrt((w[n].x-w[n-1].x)*(w[n].x-w[n-1].x)+(to-i)*(to-i));
}
double dp(int n,double to){
//当前枚举第n堵墙to的y坐标
    if(n==1)
        return count(n,w[n-1].y[1],to);
    double minn=inf;
    for(double i=w[n-1].y[1];i<=w[n-1].y[2];i+=eps)//第1个空位
        minn=min(minn,dp(n-1,i)+count(n,i,to));
    for(double i=w[n-1].y[3];i<=w[n-1].y[4];i+=eps)//第2个空位
        minn=min(minn,dp(n-1,i)+count(n,i,to));
    return minn;
}

然后呢，TLE了，我不慌，我直接调小精度：

eps=1e-2;

然后呢，出意外竟然还是TLE了，WA我都能接受啊，我直接迷茫。。。。。。

接着，我又不慌了，我想到了优化，发现到第n堵墙的时候会多次用到第n-1堵墙的同一个y坐标，于是就加个记忆化嘛，问题是y的坐标不是整数，那好办，直接化成整数就好了嘛：

const int N=20,M=10001;
const double eps=1e-3,inf=100000;
struct Node{
    double x,
        y[5];
}w[N];
double f[N][M];//表示从起点到第i堵墙j的y坐标的最小距离
double count(int n,double i,double to){
    return sqrt((w[n].x-w[n-1].x)*(w[n].x-w[n-1].x)+(to-i)*(to-i));
}
int ch(double i){
//y坐标转整，就是一个对应的关系，可以随便转，我习惯这样~~简单嘛~~
    return int(i*1000);
}
void dp(int n,double to){
    if(n==1){
        f[n][ch(to)]=count(n,w[n-1].y[1],to);
        return;
    }
    f[n][ch(to)]=inf;
    for(double i=w[n-1].y[1];i<=w[n-1].y[2];i+=eps){
        if(!f[n-1][ch(i)])
            dp(n-1,i);
        f[n][ch(to)]=min(f[n][ch(to)],f[n-1][ch(i)]+count(n,i,to));
    }
    for(double i=w[n-1].y[3];i<=w[n-1].y[4];i+=eps){
        if(!f[n-1][ch(i)])
            dp(n-1,i);
        f[n][ch(to)]=min(f[n][ch(to)],f[n-1][ch(i)]+count(n,i,to));
    }
}

然后呢，发现最后一个点还是t掉了，但是不用慌，改精度！

eps=1e-2;

然后就A了？？？，这精度是假的，提交到POJ-1566会WA，

然后已经黔驴技穷了，但是我不慌，直接拿出最后的压箱底卡精度：

eps=1e-2-(1e-3*5);

然后就又A了，皆大欢喜！

完整代码

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=20,M=10001;
const double eps=1e-2-(1e-3*5),inf=100000;
struct Node{
    double x,
        y[5];
}w[N];
double f[N][M];
double count(int n,double i,double to){
    return sqrt((w[n].x-w[n-1].x)*(w[n].x-w[n-1].x)+(to-i)*(to-i));
}
int ch(double i){
    return int(i*1000);
}
void dp(int n,double to){
    if(n==1){
        f[n][ch(to)]=count(n,w[n-1].y[1],to);
        return;
    }
    f[n][ch(to)]=inf;
    for(double i=w[n-1].y[1];i<=w[n-1].y[2];i+=eps){
        if(!f[n-1][ch(i)])
            dp(n-1,i);
        f[n][ch(to)]=min(f[n][ch(to)],f[n-1][ch(i)]+count(n,i,to));
    }
    for(double i=w[n-1].y[3];i<=w[n-1].y[4];i+=eps){
        if(!f[n-1][ch(i)])
            dp(n-1,i);
        f[n][ch(to)]=min(f[n][ch(to)],f[n-1][ch(i)]+count(n,i,to));
    }
}
int main(){
    int n;
    while(~scanf("%d",&n)){//这是POJ的代码，我懒就没改多组输入
        if(n==-1)break;
        w[0].x=0;
        w[0].y[1]=w[0].y[2]=w[0].y[3]=w[0].y[4]=5;
        for(int i=1;i<=n;i++)
            scanf("%lf%lf%lf%lf%lf",&w[i].x,&w[i].y[1],&w[i].y[2],&w[i].y[3],&w[i].y[4]);
        for(int i=0;i<=n;i++)
            for(int j=0;j<=M;j++)
                f[i][j]=0;
        w[n+1].x=10;
        w[n+1].y[1]=w[n+1].y[2]=w[n+1].y[3]=w[n+1].y[4]=5;
        dp(n+1,5);
        printf("%.2lf\n",f[n+1][ch(5)]);
    }
    return 0;
}

我恍恍惚惚就A了一道紫题。。。