uva-1347

제목 링크:https://vjudge.net/problem/UVA-1347
제목: n개의 점이 있고 x, y 좌표를 줍니다.길을 찾아 가장 왼쪽에서 출발하여 엄격하게 오른쪽으로 가다가 가장 오른쪽에 도착한 다음에 엄격하게 왼쪽으로 가장 왼쪽으로 돌아간다.-- 최단 경로가 어떻게 되나.
문제풀이를 보지 않으면 나는 정말 이 문제를 dp로 풀 수 있는지 모르겠다. 문제풀이를 보고 어리둥절한 표정을 지었다.(이 상태로 정의된 태소맥)
대체적인 사고방식: dp(i, j)로 A가 i까지 갔고 B가 j까지 갔을 때의 상태는 종점까지 얼마나 가야 하는지를 나타낸다. dp(i, j)==dp(j, i)를 증명할 수 있다.dp(i, j)는 이미 이 상태에 도달한 후에 얼마나 더 멀리 종점에 도착해야 하는지를 나타낸다. 이 상태에 어떻게 도달하는지와는 관계가 없기 때문에 dp(i, j)와 dp(j, i)는 단지 두 사람의 역할이 바뀌었을 뿐이다.그러나 이것은 dp(i, j)가 i, j 사이의 어떤 점이 지나갔는지 알 수 없기 때문에 우리는 더 많은 생각을 해야 한다. 방금 우리가 언급한 dp(i, j)==dp(j, i)라면 우리는 시종일관 i>=j(종점과 기점만 달성하는 것과 같다).만약 j>i가 된다면 A, B의 캐릭터만 교환하면 됩니다. i를 j, j를 i로 바꿉니다.이 조건이 생긴 후에 우리는 dp(i, j)를 다음과 같이 규정할 수 있다. A는 i, B는 j(i>=j)에 있고 i 이전의 모든 점은 지나갔다. 이렇게 해도 누락되지 않는다. 왜?우리의 자연스러운 방법에서 i~j 사이가 지나갔는지 모르겠다. 왜냐하면 우리는 A가 P1->P5->P6를 연속적으로 걷는 것을 허락했기 때문이다. 예를 들어 A는 P1->P2에서 걷고 B는 P1->P2에서 걷는다.그래서 P3, P4 우리는 A나 B에게 갔는지 모르겠다. 왜냐하면 우리는 A가 P6에 갔고 B가 P2에 갔는지만 알고 있기 때문이다.그러나 방금 그 예에서 P3, P4 이후에는 반드시 B에게 가야 한다는 것을 분명히 발견했다.그래서 우리가 개선한 dp(i, j)에서는 A와 B를 한 칸 한 칸 가게 할 수 있다. A가 가든지 B가 가든지 (사실은 순서가 바뀌었을 뿐이다).방금 논증한 바와 같이 우리의 상태 이동은 다음과 같다. dp[i][j]=min(DP(i+1,j)+dist(i,i+1),DP(i+1,i)+dist(j,i+1)).즉, A가 가든지 B가 가든지 A가 가든지 하면 상태 dp(i+1, j)로 간다.B가 가면 상태 dp(i, i+1)까지 가면 요구가 뒤보다 앞서기 때문에 dp(i, i+1)==dp(i+1, i)만 가면 된다.dist(i, j)는 i-j의 거리를 나타냅니다.

#include 

#include <string.h>

#include 
#include 
using namespace std;
const int N = 105;
const double INF = 0x3f3f3f3f3f3f3f3f;
int n;
double x[N], y[N], dp[N][N];
inline double dis (int a, int b) {

    return sqrt((x[a]-x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a]-y[b]));

}
void init () {
    for (int i = 1; i <= n; i++)

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

    memset(dp, 0, sizeof(dp));

    dp[2][1] = dis(1, 2);

}
double solve () {

    for (int i = 3; i <= n; i++) {

        dp[i][i-1] = INF;
        for (int j = 1; j < i-1; j++) {

            dp[i][i-1] = min(dp[i][i-1], dp[i-1][j] + dis(i, j));

            dp[i][j] = dp[i-1][j] + dis(i, i-1);

        }

    }
    double ans = INF;

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

        ans = min(ans, dp[n][i] + dis(n, i));

    return ans;

}
int main () {

    while (scanf("%d", &n) == 1) {

        init ();

        printf("%.2lf
", solve ());

    }

    return 0;

마지막으로 이 블로거에게 감사합니다:https://blog.csdn.net/qq_28236309/article/details/51931816
전재 대상:https://www.cnblogs.com/kayiko/p/10957858.html