URAL 1143 Electric Path(방향이 있는 구간 DP + 기억형 검색)

제목:
n개의 점이 있는데 그들은 마침 튀어나온 다각형을 형성하고 어떤 점에서부터 시작하며 점마다 한 번만 지나면 최종적으로 가장 짧은 경로가 된다.
흑서 133면, 고민하는 개구리.엇비슷한 제목.
아이디어:
1. 먼저 경로가 교차할 수 없으며 교차하지 않은 상태에서만 가장 짧은 경로를 찾을 수 있다.
2. dp[s, L, 0]는 s점에서 출발하여 L개의 점을 거쳐 최종적으로 가장 짧은 경로를 나타낸다. 1에서 확정할 수 있는 것은 이 L개의 점은 틀림없이 서로 인접한 것이다.
dp[s, L, 1]는 s+L - 1시에서 출발하여 L 개의 점을 거쳐 최종 최단 경로를 나타낸다.
3. 상기는 방향을 가진 구간 DP로 이해할 수 있다. 예를 들어 구간은 [0, n-1]이고 경로가 교차할 수 없기 때문에 0에서 출발할지 n-1에서 출발할지 고려한 다음에 구간을 점차적으로 축소하여 해답을 구하는 목적을 달성한다.
4. 1에서 출발하면 2 또는 n만 방문해야 가장 좋고 최종적으로 기억화 검색을 이용하여 완벽하게 해결할 수 있다.
 

#include <iostream>

#include <algorithm>

using namespace std;



const int MAXN = 210;

double dis[MAXN][MAXN], x[MAXN], y[MAXN];

double dp[MAXN][MAXN][2];

int n;



inline double getdist(int i, int j) {

    return sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));

}



double solvedp(int s, int l, int f) {

    if (dp[s][l][f] != 1e20)

        return dp[s][l][f];



    if (f == 0) {

        dp[s][l][0] = solvedp((s+1)%n, l-1, 0) + dis[s][(s+1)%n];

        dp[s][l][0] = min(dp[s][l][0], solvedp((s+1)%n, l-1, 1) + dis[s][(s+l-1)%n]);

    } else {

        dp[s][l][1] = solvedp(s, l-1, 1) + dis[(s+l-1)%n][(s+l-2)%n];

        dp[s][l][1] = min(dp[s][l][1], solvedp(s, l-1, 0) + dis[(s+l-1)%n][s]);

    }

    return dp[s][l][f];

}



int main() {

    while (~scanf("%d", &n)) {

        for (int i = 0; i < n; i++)

            scanf("%lf%lf", &x[i], &y[i]);



        for (int i = 0; i < n; i++)

            for (int j = i; j < n; j++)

                dis[i][j] = dis[j][i] = getdist(i, j);



        for (int i = 0; i < n; i++)

            for (int j = 0; j <= n; j++)

                dp[i][j][0] = dp[i][j][1] = 1e20;



        for (int i = 0; i < n; i++)

            dp[i][1][0] = dp[i][1][1] = 0.0;



        double ans = 1e20;

        for (int i = 0; i < n; i++)

            ans = min(ans, solvedp(i, n, 0));



        printf("%.3lf
", ans);

    }

    return 0;

}