BOJ)10272 현상금 사냥꾼 김정은

문제:icpc.me/10272

왼쪽 부터 오른쪽으로 순회한 뒤 순회하지 않은 정점들을 오른쪽에서 왼쪽으로 다시 순회할 때 이동거리의 최솟값을 구하는 문제이다.

이 문제는 바이토닉 투어 문제이므로 N^2 다이나믹 프로그래밍으로 해결할 수 있다.

우선 바이토닉 투어 문제는 dp[x][y]라는 테이블을 세울 수 있다. 이 때 x.는 갈 때 y는 올 때 까지 커버한 정점들의 수 이다.

점화식을 세울 때 현재 x,y까지 커버했다면 다음에 커버해야 할 정점은 당연히 max(x,y)+1이 되므로 이 정점을 갈 때 커버할 지 올 때 커버할지만 결정해주면 된다.

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int t, n;
double dp[555][555];
pair<double, double> d[555];
double getdist(pair<double, double> x, pair<double, double> y) {
    return sqrt((x.first - y.first)*(x.first - y.first) + (x.second - y.second)*(x.second - y.second));
}
double func(int x, int y) {
    if (x == n - 1 || y == n - 1) {
        if (y != n - 1)return getdist(d[y], d[n - 1]);
        if (x != n - 1)return getdist(d[x], d[n - 1]);
        return 0.0;
    }
    double &ret = dp[x][y];
    if (ret != -1.0)return ret;
    int nxt = max(x, y) + 1;
    ret = 1e11;
    ret = min(ret, func(nxt, y) + getdist(d[x], d[nxt]));
    ret = min(ret, func(x, nxt) + getdist(d[y], d[nxt]));
    return ret;
}
int main() {
    scanf("%d", &t);
    while (t--) {
        for (int i = 0; i < 555; i++) {
            for (int j = 0; j < 555; j++)
                dp[i][j] = -1.0;
        }
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%lf%lf", &d[i].first, &d[i].second);
        printf("%.3lf\n", func(0, 0));
    }
    return 0;
}