UVa1347 Tour

자서의 분석을 보고 나서야 손을 댔다.두 사람이 서로 다른 길로 출발점에서 종점까지 걸어간다고 상상해 보세요.dp(i, j)는 1~max(i, j)가 모두 지나갔고 두 사람의 위치는 각각 i와 j로 얼마나 더 가야 하는지를 나타낸다.규정i>j, i와 j는 특정한 사람을 가리키지 않고 현재 앞과 뒤에 있는 사람을 가리킨다.

#include <iostream>    
#include <stdio.h>    
#include <cmath>    
#include <algorithm>    
#include <iomanip>    
#include <cstdlib>    
#include <string>    
#include <memory.h>    
#include <vector>    
#include <queue>    
#include <stack>    
#include <map>  
#include <set>  
#include <ctype.h>    
#define INF 1000000  
#define ll long long

  
using namespace std;  

struct point{
	int x;
	int y;
};

point pt[100];

int n;
double dp[100][100];

double dist2(point p1,point p2){
	return sqrt((double)(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}

double fun(int i,int j){
	if(dp[i][j]>0)return dp[i][j];
	if(i==n){
		dp[i][j]=dist2(pt[j],pt[n]);
		return dp[i][j];
	}
	
	double re=min(fun(i+1,j)+dist2(pt[i],pt[i+1]),fun(i+1,i)+dist2(pt[j],pt[i+1]));
	dp[i][j]=re;
	return re;
}

int main(){
	
	while(cin>>n){
		for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)dp[i][j]=-1.0;
		for(int i=1;i<=n;i++){
			cin>>pt[i].x>>pt[i].y;
		}
		printf("%.2lf
",fun(1,1));
	}
	return 0;
}