POJ-2677: Tour

keyword

動的計画法　C++

問題概要

2次元平面上にN(ForumによるとN<=50)個の点があり、全てのx座標は異なる。x座標が一番小さい点から出発して全ての点を一度ずつ訪ねて戻ってくる。ただし、訪ねた点のx座標は、単調増加→単調減少になっていなくてはならない。閉路の最小距離を求める問題。

解法

x座標の小さい方から、dp[i][右への進路の直前の番号][左への進路の直前(正しくは直後)の番号]でDPすればO(N^3)で求まる。もちろんこれは無駄があって、2つ目と3つ目のどちらかは必ずi-1になるのだからdp[i][行きor戻り][自明でない方の直前の番号]とすればO(N^2)に落ちる。実装時間11分。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

typedef pair<int,int> point;

const double INF = 1e30;
int N;
vector< point > ps;

double dist(point a, point b){
	return hypot(a.first - b.first, a.second - b.second);
}

double solve(){
	vector< vector< vector<double> > > dp(N, vector< vector<double> >(N, vector<double>(N, INF)));
	dp[0][0][0] = 0;
	for(int i=0; i<N-1; i++)for(int j=0; j<N; j++)for(int k=0; k<N; k++)if(dp[i][j][k] != INF){
		dp[i+1][i+1][k] = min(dp[i+1][i+1][k], dp[i][j][k] + dist(ps[i+1], ps[j]));
		dp[i+1][j][i+1] = min(dp[i+1][j][i+1], dp[i][j][k] + dist(ps[i+1], ps[k]));
	}
	double ret = INF;
	for(int j=0; j<N; j++){
		ret = min(ret, dp[N-1][j][N-1] + dist(ps[N-1], ps[j]));
	}
	for(int k=0; k<N; k++){
		ret = min(ret, dp[N-1][N-1][k] + dist(ps[N-1], ps[k]));
	}
	return ret;
}

int main(){
	while(scanf("%d",&N)!=EOF){
		ps.clear();
		for(int i=0; i<N; i++){
			int x, y;
			scanf("%d%d",&x,&y);
			ps.push_back( point(x,y) );
		}
		printf("%.2f\n", solve());
	}
	return 0;
}