DP

---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

2D/0D

状态数n^2 决策数2

O(n*n)

---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 30ms

├ 测试数据 07：答案正确... 110ms

├ 测试数据 08：答案正确... 30ms

├ 测试数据 09：答案正确... 90ms

├ 测试数据 10：答案正确... 100ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：360ms

ms哪本书上说这是网络流的。。。

第101个过的..永远被阻挡在排行榜门外..欲哭无泪``

不过`虽然AC..大牛们的思想还素米完全弄明白\`

每个点的坐标为(x,y)(-2^31

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 25ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：59ms

likewind大牛的算法好经典!!!!!!!!

这里是个巧妙的换位咯...

相当于,把第一个人定在i-1位上,然后,通过枚举中间值k使第二个人从k达到i,然后两个人再换位....

为什么f:=f+d[k,i](j=i-1,k

chnlkw大牛的方法是正确而高效的..........

在P4M 1.2GHZ上50ms可以出1000的答案.........

但是，为何可以不像很多书上那样考虑另一条路呢？

即这段为何可以不要？

/*for(k=j+1;kF+Link[j*1000+k])

now=F+Link[j*1000+k];*/

应该是吧,我就是这样过的.

是否需要经过每一个点。急需！！！！

如果按DP做，必须有一个条件--没有两个以上的点横坐标相同，但题目中似乎漏掉了这一条件，或者本身没有这条件但数据恰好满足，但无论如何请作者或管理员修正题目描述或数据，避免会做的人因为考虑太多而放弃。

readln(px[i],py[i]);

WA 4组

read(px[i],py[i]);

AC.....

数据有问题？

环游的路线只能是从最西端单向到最东端，再单向返回最西端.

是单向!!!

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

const int maxn = 1100;
const int inf = 0x7fffffff;
int n;
double x[maxn];
double y[maxn];
int r[maxn];
double f[maxn][maxn];

bool cmp (int a, int b) {
    return x[a] < x[b];
}

double dist (int a, int b) {
    return sqrt ((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]));
}

int main ()
{
    freopen ("in.txt", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
        r[i] = i;
    }
    sort (r + 1, r + n + 1, cmp);
    for (int i = 1; i <= n - 2; i++) {
        f[n - 1][i] = dist (r[n], r[n - 1]) + dist (r[i], r[n]);
    }
    for (int i = n - 2; i > 1; i--) {
        for (int j = 1; j < i; j++) {
            f[i][j] = min (f[i + 1][j] + dist (r[i], r[i + 1]), f[i + 1][i] + dist (r[i + 1], r[j]));
        }
    }
    double ans = f[2][1] + dist (r[1], r[2]);
    cout << setprecision (2) << setiosflags (ios::fixed) << ans;
    return 0;
}

点击查看程序源码+详细题解

vijos彩字。。怎么打= =

Accepted 有效得分：100 有效耗时：0ms

noip09前最后一题,,,搞定睡觉....

谁能给几组数据啊

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 56ms

├ 测试数据 06：答案正确... 322ms

├ 测试数据 07：答案正确... 478ms

├ 测试数据 08：答案正确... 556ms

├ 测试数据 09：答案正确... 494ms

├ 测试数据 10：答案正确... 509ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2415ms

没想到数据这么大，我把sqrt改成三角函数了。。。