Tour - UVa 1347 dp
2901 단어 UVadp동적 기획 및 추이
Write a program that, given a set of n points in the plane, computes the shortest closed tour that connects the points according to John's strategy.
Input
The program input is from a text file. Each data set in the file stands for a particular set of points. For each set of points the data set contains the number of points, and the point coordinates in ascending order of the x coordinate. White spaces can occur freely in input. The input data are correct.
Output
For each set of data, your program should print the result to the standard output from the beginning of a line. The tour length, a floating-point number with two fractional digits, represents the result.
Note: An input/output sample is in the table below. Here there are two data sets. The first one contains 3 points specified by their x and y coordinates. The second point, for example, has the x coordinate 2, and the ycoordinate 3. The result for each data set is the tour length, (6.47 for the first data set in the given example).
Sample Input
3
1 1
2 3
3 1
4
1 1
2 3
3 1
4 2
Sample Output
6.47
7.89
제목: x축에 따라 정렬하여 점을 주고 가장 왼쪽에서 가장 오른쪽까지의 점을 구하고 다시 돌아온 경로의 최소값을 구한다.
사고방식: 두 선이 왼쪽에서 오른쪽으로 보이고 dp[i][j]는 1-max(i, j)의 점이 모두 지나간 후의 가장 짧은 경로를 나타낸다.두 경로는 반드시 x의 작은 점에서 x의 큰 점으로 운동하는 것이기 때문에 되돌아오는 상황은 결과를 더욱 크게 할 것이다.
AC 코드는 다음과 같습니다.
#include
#include
#include
#include
using namespace std;
double dp[1010][1010],INF=1000000000;
int x[1010],y[1010];
double dis(int a,int b)
{ return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
int main()
{ int n,i,j,k;
while(~scanf("%d",&n))
{ for(i=1;i<=n;i++)
scanf("%d%d",&x[i],&y[i]);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
dp[i][j]=INF;
dp[1][1]=0;
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
{ dp[j][j]=min(dp[j][j],dp[i][j]+dis(i,j));
dp[i][j+1]=min(dp[i][j+1],dp[i][j]+dis(j,j+1));
dp[j][j+1]=min(dp[j][j+1],dp[i][j]+dis(i,j+1));
}
printf("%.2f
",dp[n][n]);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
UVa 110 순환 정렬 프로그램 없음제목: Pascal의 정렬 프로그램을 구성합니다.처음에 보면 Pascal 프로그램을 썼는데 모르는 것은 어려울 줄 알았지만 사실은 프로그램의 대부분이 고정되어 있고 직접printf를 쓰면 된다. 주로 비교적인if-e...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.