如果不想考虑特殊情况，可以把第一个和最后一个点拆成2个点。

f[2,1]=0，其他为max

ans=f[n+2,n+1]

但是拆点要在排序以后拆……我一开始拆点直接把排序之前的第一个和最后一个拆了下……

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

日 太恶心了 交了 2 次 因为

编译通过...

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

├ 测试数据 02：运行时错误...| 错误号: 207 | 无效浮点运算

├ 测试数据 03：运行时错误...| 错误号: 207 | 无效浮点运算

├ 测试数据 04：运行时错误...| 错误号: 207 | 无效浮点运算

├ 测试数据 05：运行时错误...| 错误号: 207 | 无效浮点运算

├ 测试数据 06：运行时错误...| 错误号: 207 | 无效浮点运算

├ 测试数据 07：运行时错误...| 错误号: 207 | 无效浮点运算

├ 测试数据 08：运行时错误...| 错误号: 207 | 无效浮点运算

├ 测试数据 09：运行时错误...| 错误号: 207 | 无效浮点运算

├ 测试数据 10：运行时错误...| 错误号: 207 | 无效浮点运算

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

Unaccepted 有效得分：10 有效耗时：0ms

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

快排打错..

无语了。。很久之前过的一个题。。今天用C++又写了一个。。。WA了一下午。。

还以为自己写错了，结果发现poj也有这个题。。交上去A了:(

强烈地pat一下

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

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

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

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

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

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

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

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

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

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

1) 如果x1=x2，即A和B处在同一点，那么F(x1, x2) = F(x1, x1) = F(x1, x1 - 1) + dist(x1, x1 - 1)

2) 如果x1=x2+1，即B在A的紧邻的靠后一点，那么F(x1, x2) = F(x2, x') + dist(x1, x') (1

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

有两个要注意的地方：

1.j+1=i时 里面的循环中的状态方程式

f[i][j]=min(f[i][j],f[j][k]+dist(k,i))

而非 f[i][j]=min(f[i][j],f[k][j]+dist(k,i))

因为按照循环来看

for i:1 to n-1

for j:1 to i-1

那么j恒小于i

所以第一维应该大于第一维，虽然按照题意有f[k][j]==f[j][k]

2.被千千万万的牛们讲烂了。。。但是他们的话沉下去了。。。就再说下。。。max=10e24 int不够，要double。。

编译通过...

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

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

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

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

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

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

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

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

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

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

struct Point

{

long x,y;

static double Distance(Point a,Point b)；

};

void PointQsort(Point* a,long p,long q);

double solve(long p,long q);

double opt[1001][1001];

bool searched[1001][1001];

Point a[1001];

double solve(long p,long q)

{

if(searched[p][q])

return opt[p][q];

double result=0;

long c=std::min(p,q);

if(p==0)

result=Point::Distance(a[0],a[q]);

else if(q==0)

result=Point::Distance(a[0],a[p]);

else

result=std::min(solve(c-1,q)+Point::Distance(a[c-1],a[p]),

solve(p,c-1)+Point::Distance(a[c-1],a[q]));

searched[p][q]=true;

searched[q][p]=true;

opt[p][q]=result;

opt[q][p]=result;

return result;

}

回来一看题解。。貌似我的状态方程和你们的都不一样啊 = =

opt[i][j]=

{

min

{

opt[c-1,j]+Distance[c-1][i], //c是i,j中最小的数

opt+Distance[c-1][j],

}, (i,j>0)

Distance[0][i], (j=0)

Distance[0][j], (i=0)

}

2) 如果x1=x2+1，即B在A的紧邻的靠后一点，那么F(x1, x2) = F(x2, x') + dist(x1, x') (1

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

读取一定要用实型啊!!!

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我发现自己弱的很，做过三取方格数这种多进程DP，遇到一样的还是不能一下想到，方程感谢LS各位牛。。

编译通过...

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

├ 测试数据 02：答案错误...　├ 标准行输出

　├ 错误行输出

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

├ 测试数据 04：答案错误...　├ 标准行输出

　├ 错误行输出

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

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

├ 测试数据 07：答案错误...　├ 标准行输出

　├ 错误行输出

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

├ 测试数据 09：答案错误...　├ 标准行输出

　├ 错误行输出

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

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

Unaccepted 有效得分：60 有效耗时：34ms

const maxn=1000;

type point=record

x,y:real;

end;

var n,i,j:longint;

p:array[1..maxn] of point;

d,f:array[1..maxn,1..maxn] of real;

g:array[1..maxn,1..maxn] of boolean;

t:point;

s:real;

function dp(x1,x2:longint):real;

var t,x:longint;

min,s:real;

begin

if x1p[j].x then begin

t:=p[i]; p[i]:=p[j]; p[j]:=t; end;

for i:=1 to n do

for j:=1 to n do

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

g[1,1]:=true; f[1,1]:=0; s:=dp(n,n);

writeln(s:0:2);

end.

什么情况？

1.一定要把坐标当实数读~我已经栽过两次...

2.一定不要以为自己小小的改一个地方就会AC~也许是NC~

program v1014;

var ss:array[1..1000,1..2]of real;

n,i,j,k:longint;

f,dis:array[1..1000,1..1000]of extended;

min:extended;

procedure qk(s,t:longint);

var i,j:longint;

x,y:real;

begin

x:=ss;i:=s;j:=t;y:=ss;

while i

我无语……

max开2147483647都不过,,,

原来要开 1e24.

(Invalid img)O,YEAH!!!

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

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

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

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

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

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

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

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

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

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

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

eteced的特殊处理貌似有问题？

因为求的是个回路，那么就可以理解为A,B两个人走，同时从1点出发，两个人不走相同的点且走到n点时全部点都被走到，f就表示A走到I这个点B走到j这个点时，且之前的点全被走到的最小值，当然初始化时要排序点。优化：我们发现f一定等于f[j,I]，因为这是对称的，所以我们可以规定I>j,那么求出f，f[j,I]就等于f。问题解决

编译通过...

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

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

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

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

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

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

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

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

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

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

坐标一定要用实数存，不然会207错误》……………………

狂吐血,坐标用longint存,交了2次10分!!其余207错误

207错误的同志们注意啦---|---|---|---|---|---|---|---|---|---|---|---|---|--坐标也要用实数存!!!!!!!!!!!!!!!!!!!1