p1014.cpp

vijos动态规划5题:P1002,P1006,P1011,P1014,P1025

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define min(a, b) (((a) < (b)) ? (a) : (b))

#define MAXN 1100

typedef struct _NODE
{
    int x, y;
} NODE;

NODE node[MAXN];
double f[MAXN][MAXN] = { 0 };

double dist(const int i, const int j)
{
    double xx = node[i].x - node[j].x, yy = node[i].y - node[j].y;
    return sqrt(xx * xx + yy * yy);
}

int cmp(NODE *a, NODE *b)
{
    return a->x - b->x;
}

int main()
{
    int n, i, j, k;

    scanf("%d", &n);
    for (k = 1; k <= n; ++k)
        scanf("%d %d", &node[k].x, &node[k].y);

    qsort(&node[1], n, sizeof(node[0]), cmp);

    for (i = 1; i <= n; ++i)
        for (j = 1; j <= n; ++j)
            f[i][j] = 1e20;

    f[1][2] = f[2][1] = dist(1, 2);
    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j < i - 1; ++j)
            f[j][i] = f[i][j] = f[i - 1][j] + dist(i - 1, i);
        for (k = 1; k < j; ++k)
            f[j][i] = f[i][j] = min(f[i][j], f[i - 1][k] + dist(k, i));
    }

    printf("%.02lf\n", f[n][n - 1] + dist(n - 1, n));

    return 0;
}