Uva 1347 - Tour(DP)

제목 링크https://vjudge.net/problem/UVA-1347
[제의] x 좌표의 점증 순서에 따라 평면에 있는 n개의 점을 정하고 각 점의 x 좌표는 같지 않다(n<=1000). 당신의 임무는 하나의 노선을 설계하는 것입니다. 가장 왼쪽의 점에서 출발하여 가장 오른쪽의 점까지 갔다가 돌아오는 것입니다. 가장 왼쪽과 가장 오른쪽의 두 점을 제외하고 각 점은 한 번 지나가도록 하고 전체 노정을 최대한 짧게 해야 합니다. 두 점 사이의 길이는 그들의 유클리드 거리입니다.
[사고방식] 아무런 사고방식이 없고 심지어 dp로 할 줄은 생각지도 못했다. 자서에서 설명한 것을 보고서야 알았다.먼저 사고방식의 전환이다.'왼쪽에서 오른쪽으로 다시 돌아온다'는 이 과정을'두 사람이 동시에 가장 왼쪽에서 출발하여 두 가지 다른 경로를 따라 가다가 마지막에 모두 가장 오른쪽에 도착한다'는 상태의 디자인도 교묘하다. dp(i, j)를 설정하면 1~max(i, j)의 모든 결점이 이미 지나갔고 두 사람의 현재 위치는 i와 j이다. 이때 가장 짧은 거리는 얼마나 가야 하는가를 나타낸다.조금만 생각해 보면 dp(i, j)=dp(j, i)라는 것을 알 수 있다. 그래서 우리는 dp(i, j)에서 i>j를 만족시키도록 규정하고 있다. 그러면 어느 사람이든 다음 단계는 i+1, i+2.n으로 갈 수 있다. 그러나 예를 들어 dp(i, j)의 상태에서 만약에 어떤 사람이 직접 i+2까지 가면 상황은'1~i와 i+2가 지나갔고 i+1이 지나가지 않았다'가 된다. 이것은 표시할 수 없는 상태인데 어떡하지?이러한 상태 이동을 직접 금지한다. 즉, 이 두 사람은 어느 것이든 i+1으로만 갈 수 있고 상태 dp(i, j)는 dp(i+1, i)나 dp(i+1, i)로만 옮길 수 있다. 그리고 이렇게 하면 누락되지 않는다. 어렵지 않다는 것을 증명한다. 쉽게 말하면 첫 번째 사람이 i+2에서 i+2로 직접가면 i+1이라는 점은 두 번째 사람만 갈 수 있다. 이왕 이렇게 된 이상 두 번째 사람을 i+1으로 먼저 가게 하면 최종 결과는 변하지 않는다.상태 이동 방정식은 dp[i][j]=min {dp[i+1][j]+dis(i,i+1), dp[i+1][i]+dis(j,i+1)} 경계는 dp[n-1][x]=dis(n-1,n)+dis(x,n)로 두 사람이 모두 종점으로 가는 것이다.마지막 답은dis(1,2)+dp[2][1]

#include
using namespace std;

const double inf = 2e9;
const int maxn = 1050;

int n;
double dp[maxn][maxn];

struct Point {
    double x, y;
}p[maxn];

double dis(Point& a, Point& b) {
    return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

void d() {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) dp[i][j] = inf;
    }
    for (int j = 1; j < n - 1; ++j) {
        dp[n - 1][j] = dis(p[n - 1], p[n]) + dis(p[j], p[n]);
    }

    for (int i = n - 2; i >= 1; --i) {
        for (int j = 1; j < i; ++j) {
            dp[i][j] = min(dp[i][j], dp[i + 1][j] + dis(p[i], p[i + 1]));
            dp[i][j] = min(dp[i][j], dp[i + 1][i] + dis(p[j], p[i + 1]));
        }
    }

    double ans = dis(p[1], p[2]) + dp[2][1];
    printf("%.2lf
", ans);
}

int main() {
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; ++i) {
            scanf("%lf%lf", &p[i].x, &p[i].y);
        }
        d();
    }
    return 0;
}

전재 대상:https://www.cnblogs.com/wafish/p/10465348.html