백준10272 현상금 사냥꾼 김정은

작성일 | In

문제 링크

  • http://icpc.me/10272

문제 출처

  • 2014 GCPC C번

사용 알고리즘

  • DP

시간복잡도

  • $O(N^2)$

풀이

두 사람이 1에서 시작해 서로 다른 지점을 통해 N까지 간다고 생각하면 더 편합니다.

$D(i, j)$를 첫번째 사람은 $i$번째 지점까지, 두번째 사람은 $j$번째 지점까지 가는 최단 거리라고 정의합시다.
두 사람 중 한 사람이 $\max(i, j) + 1$로 이동해야 하므로 상태 전이는 매우 간단하게 나타낼 수 있습니다.

$O(N^2)$에 문제를 풀 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<int, int> p;

int n; p a[555];
double dp[555][555];

double dst(p s, p e){
	ll dx = s.x - e.x, dy = s.y - e.y;
	return sqrt(dx*dx + dy*dy);
}

double f(int i, int j){
	double &res = dp[i][j];
	if(res >= 0) return res;
	if(i == n) return res = dst(a[j], a[n]);
	if(j == n) return res = dst(a[i], a[n]);
	int k = max(i, j) + 1;
	return res = min(f(k, j) + dst(a[i], a[k]), f(i, k) + dst(a[j], a[k]));
}

void solve(){
	cin >> n; for(int i=1; i<=n; i++) cin >> a[i].x >> a[i].y;
	for(int i=0; i<555; i++) for(int j=0; j<555; j++) dp[i][j] = -1;
	cout << fixed << setprecision(10) << f(1, 1) << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int t; cin >> t; while(t--) solve();
}