uva 1347 - Tour(이중 유클리드)

제목 대의: n개의 점을 제시하여 각 점을 연결하는 가장 짧은 폐합 여정을 확정하는 문제.
문제풀이 사고방식: dp[i][j]는 i에서 1로, 그리고 1에서 j까지의 거리를 나타낸다.
dp[i][j] = dp[i-1][j] + dis(i,i-1);
dp[i][i-1] = min (dp[i][i-1], dp[i-1][j] + dis(i, j));
기억 코드:

//0 KB 58 ms
#include
#include
#include
#include
#include
using namespace std;
int n;
double dis[1010][1010];
pairpoint[1010];
double dp[1010][1010];
double dist(int x,int y)
{
    return sqrt((point[x].first-point[y].first)*(point[x].first-point[y].first)+(point[x].second-point[y].second)*(point[x].second-point[y].second));
}
double getdp(int x,int y)
{
    double &ans=dp[x][y];
    if(ans>=0) return ans;
    if(x==n-1){
        ans=dis[n-1][n]+dis[y][n];
        return ans;
    }
    ans=min(getdp(x+1,y)+dis[x][x+1],getdp(x+1,x)+dis[y][x+1]);
    return ans;
}
int main()
{
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++){
            scanf("%lf%lf",&point[i].first,&point[i].second);
          //  printf("%f %f",point[i].first,point[i].second);
            for(int j=1;j<=i-1;j++){
                dis[i][j]=dis[j][i]=dist(i,j);
            }
        }
        memset(dp,-1,sizeof(dp));
        printf("%.2f
",getdp(1,1));
    }
    return 0;
}

반복:

//0 KB 12 ms
#include
#include
#include
#include
#include
using namespace std;
int n;
double dis[1010][1010];
pairpoint[1010];
double dp[1010][1010];
double dist(int x,int y)
{
    return sqrt((point[x].first-point[y].first)*(point[x].first-point[y].first)+(point[x].second-point[y].second)*(point[x].second-point[y].second));
}
int main()
{
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++){
            scanf("%lf%lf",&point[i].first,&point[i].second);
            for(int j=1;j<=i-1;j++){
                dis[i][j]=dis[j][i]=dist(i,j);
            }
        }
        for(int i=1;i=1;i--)
        for(int j=1;j<=i;j++){
            if(j==i&&i!=1) break;
            dp[i][j]=min(dp[i+1][j]+dis[i][i+1],dp[i+1][i]+dis[j][i+1]);
        }
        printf("%.2f
",dp[1][1]);
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

P1722 매트릭스 II & P1044 창고 문제풀이

블로그 원제 링크 1 1 1 1 1 원제 링크 2, 2, 2. 먼저 P1722\text{P1722} P1722를 살펴보겠습니다. 제목 요약: 하나 있다× n 2\times n 2×n의 격자, 현재 너는 그것들의 모든...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

uva 1347 - Tour(이중 유클리드)

좋은 웹페이지 즐겨찾기