10272번: 현상금 사냥꾼 김정은

https://www.acmicpc.net/problem/10272


$O(tn^2)$

1-> a1 -> a2 -> ... -> x -> ... -> y -> ... -> b2 -> b1 ->1 인 루트를 생각하자.
dp[x][y] : (1-> a1 -> a2 -> ... -> x 경로 거리) + (y -> ... -> b2 -> b1 ->1 경로 거리)의 최소값
점화식을 통해 답을 구한다.
비슷한 문제가 꽤 많은데, koi 중에는 경찰차 문제가 있다.

#include<cstdio>
#include<algorithm>
#define dis(a,b) sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]))
using namespace std;
int t, n, x[512], y[512];
double dp[512][512];
double f(int l, int r) {
    if (r == n - 1) return dis(l, r);
    if (dp[l][r]) return dp[l][r];
    return dp[l][r] = min(f(l, r + 1) + dis(r, r + 1), f(r, r + 1) + dis(l, r + 1));
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)scanf("%d %d", x + i, y + i);
        fill(&dp[0][0], &dp[511][512], 0);
        printf("%lf\n", f(0, 0));
    }
    return 0;
}