uva 1347 tour

题意:平面上有n个点,所有点的x坐标均不同,两点之间的花费为两点之间的欧几里得距离,从最左面出发,到最右面返回

所有点除最左和最右路过两次,其他的路过一次,输出最小花费

分析:按照题意无法定义路过点的状态,把路径理解为两个人同时从最左出发,到达最右点,中间的点只能一个人走且只能一次,这样就可以用(i,j)表示两个人分别在点i和点j的,但是无法表示哪个点走没走过

强制规定i>j,j以前的点都走过了,这样就可以表示出走过点的状态,那么(i,j)只能向(i+1,j)和(i+1,i)转移

我用dp[i][j]表示一个人走到(i,j)这个状态的最小花费

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
const double INF=0x3f3f3f3f;
double dp[maxn][maxn],x[maxn],y[maxn];

double dis(int i,int j){
    double dx=x[i]-x[j];dx*=dx;
    double dy=y[i]-y[j];dy*=dy;
    return sqrt(dx+dy);
}

int main(){
    int n;
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++)
          scanf("%lf%lf",x+i,y+i);
        memset(dp,0,sizeof(dp));
        dp[2][1]=dis(2,1);
        for(int i=3;i<=n;i++){
            dp[i][i-1]=INF;
            for(int j=1;j<i-1;j++){
                dp[i][j]=dp[i-1][j]+dis(i-1,i);
                dp[i][i-1]=min(dp[i][i-1],dp[i-1][j]+dis(j,i));
            }
        }
        //答案就是min(dp[n][j]+dis(j,n))
        double ans=INF;
        for(int i=1;i<n;i++)
          ans=min(ans,dp[n][i]+dis(n,i));
        printf("%.2f
",ans);
    }
    return 0;
}
View Code
原文地址:https://www.cnblogs.com/jihe/p/5224965.html