/*
醉了醉了~
这题弄了一下午一直只能过样例+第一个点
这是为啥呢
然后才发现INF傻逼一般地打成了int型，然后一改double瞬间AC
悲伤的故事
这是一道痕经典的动规问题吧
lrj紫书上dp一章P269有~
f[ i ][ j ]表示第一个人走到i，第二个人走到j 的最短路径，
要求i<j，且0到j的点都被经过了(因为f[i][j]和f[j][i]等效，所以可以减少枚举)
这样很容易想到，j+1的点不是被第一个人走，就是被第二个人走
考虑到找前驱状态很麻烦~我们就可以找后继状态去刷新他们的值
也就是刷表法了~~
所以有转移方程
f[ i ][ j+1]=min{ f[ i ] [ j ]+d[ j ] [ j +1] }
f[ j ] [ j+1 ]=min{ f[ i ][ j ]+d[ i ][ j+1 ] }
初值f[0][1]=d[0][1](d[i][j]表示第i个点到第j个点的距离)
即可以发现对于某个状态来说，他可以连锁更新两个状态，
即f[i][j+1],f[j][j+1]
嗯第一个方程应该很好解释了
就是第二个人走到下一个点的情况
第二个方程可以这么理解，
两个人可以指前面一个人，和后面一个人，
当后面的人走到前面，当然就对换过来了，不影响结果
即两个人是不区分的，只是一个前面一个后面，因为是等效的
所以当后面这个人走到j+1位置的时候，那肯定会有原来走的更前的那个人
变成了更后的那个人，即变成了f[j][j+1]
(好好理解一下)
这样就不难操作了，我们先预处理一下数据
对于读进的数，我们按从横坐标从小到大排序
然后预处理距离d[][]，用勾股定理求坐标距离就好了
注意不管是f[][]还是d[][]我们都只需要求f[i][j](i<j)即可
然后再扫描一遍求所有状态的可能情况(不包括终点)
我们的f[][n]表示的是前面那个人走到了n点了
但是后面那个人还没有到n点
如果要完成一个哈密尔
顿回路的话就还差了后面那个人到n点的距离
所以答案就是min{f[i][n]+d[i][n]}
所以遍历一下这n-1种状态就好了>3<
好题~
*/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const double INF=1e30;
const int MAXN=1003;
struct node
{
    double x,y;
    bool operator<(const node&b)const
    {
        return x<b.x;
    }
}a[MAXN];
int n;
double ans=INF;
double f[MAXN][MAXN];
double d[MAXN][MAXN];

double getd(int i,int j)
{
    double x=fabs(a[i].x-a[j].x);
    double y=fabs(a[i].y-a[j].y);
    return sqrt(x*x+y*y);
}

void init()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            d[i][j]=getd(i,j),f[i][j]=INF;
}

void DP()
{
    f[1][2]=d[1][2];
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            f[i][j+1]=min(f[i][j+1],f[i][j]+d[j][j+1]);
            f[j][j+1]=min(f[j][j+1],f[i][j]+d[i][j+1]);
        }
    for(int i=1;i<=n-1;i++)  
        ans=min(ans,f[i][n]+d[i][n]);  
    printf("%.2lf\n",ans);
}

int main()
{
    init();
    DP();
}

//P1523 100pts
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 1e50
#define MAXN 1010
#define dbl double
using namespace std;
struct node{
dbl x;
dbl y;
bool operator<(const node &rhs)const{
return x<rhs.x;
}//按照纵坐标从左往右排序
}arr[MAXN];
int n;
dbl f[MAXN][MAXN];
inline dbl dis(int x,int y){
return hypot(fabs(arr[x].x-arr[y].x),fabs(arr[x].y-arr[y].y));
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%lf%lf",&arr[i].x,&arr[i].y);
}
sort(arr+1,arr+1+n);//排序
// for(int i=1;i<=n;++i){
// printf("%lf %lf\n",arr[i].x,arr[i].y);
// }
for(int i=0;i<=1000;++i){
for(int j=0;j<=1000;++j){
f[i][j]=INF;
}
}
f[2][1]=dis(1,2);
// printf("f[2][1]=%lf\n",f[2][1]);
for(int i=3;i<=n;++i){
for(int j=i-1;j>=1;--j){
if(i==j+1){
//刚好是向后一个的节点
for(int k=j-1;k>=1;--k){
f[i][j]=min(f[i][j],f[j][k]+dis(k,i));
}
}else{
f[i][j]=min(f[i][j],f[i-1][j]+dis(i-1,i));
}
}
}
double ans=INF;
for(int i=1;i<=n;++i){
ans=min(ans,f[n][i]+dis(i,n));
}
// printf("\n");

printf("%.2lf\n",ans);
}

参照楼上大神的代码，完成AC。在这留下c++代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 1100;
const int M = 150;
double dp[N][N];
int n,m,t;
struct opint
{
double x,y;
bool operator <(const opint &k)const
{
if(k.x == x)
return y < k.y;
else
return x < k.x;
}
}s[N];
double Dis(int a, int b)
{
return sqrt((s[a].x - s[b].x) * (s[a].x - s[b].x) + (s[a].y - s[b].y) * (s[a].y - s[b].y));
}
int main()
{
while(~scanf("%d",&n))
{
for(int i = 0; i < n; i++)
scanf("%lf%lf",&s[i].x,&s[i].y);
for(int i = 0; i < n; i++)
fill(dp[i],dp[i]+n,1e60);
sort(s,s+n);
dp[0][0] = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
{
int k = min(n-1,max(i,j) + 1);
dp[i][k] = min(dp[i][k],dp[i][j] + Dis(j,k));
dp[k][j] = min(dp[k][j],dp[i][j] + Dis(i,k));
}
printf("%.2lf\n",dp[n-1][n-1]);
}
}

program p1014;

type

rec=record

x,y:real;

end;

shuzu=array[0..1200] of rec;

var

a:shuzu;

f:array[0..1200,0..1200] of real;

n,i,j,k:integer;

function dis(i,j:integer):real;

begin

dis:=sqrt(sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y));

end;

function min(c,d:real):real;

begin

if c>d then c:=d;

min:=c;

end;

procedure q(var a:shuzu; l,r:integer);

var

i,j:integer; tp:rec; t:real;

begin

i:=l;

j:=r;

t:=a[(l+r) div 2].x;

while i

题意：本题是求一从点1到点n再回点1的回路，且此回路必须经过所有点一次。另外

从1到n的路必须从左到右，从n到1的路必须从右到左。

分析：初看此题目发现很难确定哪些点是在从1到n才路上，哪些是从n回1的路上，

若想对其进行枚举，枚举时间本身就会超过题目限制。再进行深入分析，发现2条路线

可以视为2条从1到n的路。我们可以把前i个点分配给第1条路（以后称路1）或第2条路

（以后称为路2），我们并不需要详细记录每个点属于哪一条路，只要记录下路1当前最

后一个点p，路2最后一个点为q，用F[p，q]表示此时的最优解。

继续研究发现路1与路2完全交换不影响F的直。即F[p,q]=F[q,p]，故可以令路2最后一点永远

大于路1最后一点。

若前i个点已经分入2条路中，则可以得到F[1，i]，F[2，i]，F[3,i]。。。F

第i+1个点可能连入路1，则将得到F=min（F[1，i]+L（1，i+1），F[2，i]+L（2，i+1），。。。，

F+L(i-1,i+1));

L(i,j) 表示点i和点j的直线距离

第i+1个点如连如路2，则将得到（K=1 to i-1） F[K，i+1]=f[k,i]+L;

当求完n-1个点后再把路1路2最后一点均与n点连接即可以得到题目所求回路距离，选出其中最小一个为最优解。

//P1523 100pts 
#include<cmath> 
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 1e50 
#define MAXN 1010
#define dbl double
using namespace std;
struct node{
    dbl x;
    dbl y;
    bool operator<(const node &rhs)const{
        return x<rhs.x;
    }//按照纵坐标从左往右排序 
}arr[MAXN];
int n;
dbl f[MAXN][MAXN];
inline dbl dis(int x,int y){
    return hypot(fabs(arr[x].x-arr[y].x),fabs(arr[x].y-arr[y].y));
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%lf%lf",&arr[i].x,&arr[i].y);
    } 
    sort(arr+1,arr+1+n);//排序
//  for(int i=1;i<=n;++i){
//      printf("%lf %lf\n",arr[i].x,arr[i].y);
//  }
    for(int i=0;i<=1000;++i){
        for(int j=0;j<=1000;++j){
            f[i][j]=INF;
        }
    }
    f[2][1]=dis(1,2);
//  printf("f[2][1]=%lf\n",f[2][1]);
    for(int i=3;i<=n;++i){
        for(int j=i-1;j>=1;--j){
            if(i==j+1){
                //刚好是向后一个的节点
                for(int k=j-1;k>=1;--k){
                    f[i][j]=min(f[i][j],f[j][k]+dis(k,i));
                } 
            }else{
                f[i][j]=min(f[i][j],f[i-1][j]+dis(i-1,i));
            }
        }
    }
    double ans=INF;
    for(int i=1;i<=n;++i){
        ans=min(ans,f[n][i]+dis(i,n));
    }
//      printf("\n");
    
    printf("%.2lf\n",ans);
}

同是只过了样例和一个点，也是int inf。。。
不过还多犯了一个错误，i和j打反了。。
感觉这个DP很棒，维护一个曲线（可能自交），然后利用曲线长度取最小值的时候一定不会自交，一定是题目要求的那种样子，然后取一个特殊情形就是封闭成回路的情况。

状态 耗时 内存占用

#1 Accepted 6ms 2.375 MiB
#2 Accepted 4ms 2.5 MiB
#3 Accepted 6ms 4.734 MiB
#4 Accepted 5ms 3.137 MiB
#5 Accepted 14ms 10.621 MiB
#6 Accepted 36ms 15.5 MiB
#7 Accepted 39ms 15.5 MiB
#8 Accepted 40ms 15.504 MiB
#9 Accepted 37ms 15.484 MiB
#10 Accepted 40ms 15.371 MiB

初始化大一点……
###Block Code
double mmin=11111111111111.0;
rep(k,1,j){
if(f[j][k]==-1)
f[j][k]=dp(j,k);
mmin=min(mmin,f[j][k]+d[i][k]);
}

这道题目纠结了我3天。。总算是弄清楚了。。

首先要声明：数据中不存在同一个x坐标上有多于2个点的情况！

状态的表示很容易想到。。由于只能单向前进（不管是从西向东还是从东向西）。。所以只要走过的点是不可能再在后面的规划中遇到的。。也就是说。。如果将题目考虑成同时有两个从西往东走。。那么每一个坐标点必然会**立即**加入两条路线中的一条。。于是。。我们可以用f[i][j]表示当前两条路线的最后一个点分别是i和j。。f[i][j]隐含的一个意思是：对于所有kj因为不难发现f的对称性，即f[i][j]=f[j][i]。。接下来的事情就是分析f[i][j]能够由哪些状态转移得到。。

由于规定i>j。。故而为了维护这个性质。。新加入的点

f=min{f[k,i-1]+min{dist[k,i]+dist,dist[k,j]+dist} (1

编译通过...

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

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

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

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

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

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

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

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

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

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

program ex;

var f:array[0..1001,0..1001] of real;

x,y:array[0..1001] of real;

i,j,n:longint;

function min(a,b:real):real;

begin

if a>b then exit(b)

else exit(a);

end;

procedure swap(var a,b:real);

var t:real;

begin

t:=a;a:=b;b:=t;

end;

function dist(i,j:longint):real;

begin

exit(sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j])));

end;

begin

readln(n);

for i:=1 to n do

readln(x[i],y[i]);

for i:=1 to n-1 do

for j:=i+1 to n do

if x[i]>x[j] then

begin

swap(x[i],x[j]);

swap(y[i],y[j]);

end;

for i:=2 to n do

f:=f+dist(i,i-1);

for i:=2 to n do

for j:=2 to i do

f:=min(f+dist(j,j-1),f[j,j-1]+dist(i,j-1));

writeln(f[n,n]:0:2);

end.

秒杀

到底是怎么给你们想到的

f[i]=min(f[j]+sum[j,i]-dist[j-1,j]+dist[j-1,i])

f[i]表示到第i个节点的最小回路。枚举由哪个点断开回路连向第i个节点。

时间、空间O(n^2)

编译通过...

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

├ 测试数据 02：运行时错误...|错误号: 207

├ 测试数据 03：运行时错误...|错误号: 207

├ 测试数据 04：运行时错误...|错误号: 207

├ 测试数据 05：运行时错误...|错误号: 207

├ 测试数据 06：运行时错误...|错误号: 207

├ 测试数据 07：运行时错误...|错误号: 207

├ 测试数据 08：运行时错误...|错误号: 207

├ 测试数据 09：运行时错误...|错误号: 207

├ 测试数据 10：运行时错误...|错误号: 207

怎么回事

比较简单。。。

题解：

http://lifeich1.spaces.live.com/blog/cns!9AB465A9D807BE22!194.entry

program lv_you_shang_jian_hua_ban;

const maxn=1010;

var a,b:array[0..maxn,0..maxn]of real;

x,y:array[0..maxn]of real;

i,j,k,m,n,o,u,p,q:longint;

ans:real;

procedure sort(p,q:longint);

var i,j:longint; g,k:real;

begin

i:=p; j:=q;

k:=x[(p+q) shr 1];

repeat

while kx[i] do inc(i);

if ij;

if (p

题解：

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

const filename='p1014';

var

x,y:array[1..1000]of double;

f:array[1..1000,1..1000]of double;

i,j,n:longint;

function dist(i,j:longint):double;

begin exit(sqrt(sqr(x[i]-x[j-1])+sqr(y[i]-y[j-1]))); end;

function min(a,b:double):double;

begin if a>b then exit(b);exit(a);end;

procedure qsort(l,r:longint);

var i,j:longint;xx,yy:double;

begin

i:=l;j:=r;xx:=x[l];yy:=y[l];

while(i

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

....初始化小了晕。。害我交了3次。。。

我的方法可能有点麻烦了。。。

先初始化。。

F表示第1条路到I点，第2条路到J点。

I 1 TO N

J 1 TO I-1

如果 I-1>J

直接F由F推出。

如果I-J

F：=MIN{F[H，J]+V[H，I]}（1〈=H〈=J-1）

答案MAX{F[N，I]+V}（1〈=I〈N）