编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

求本题DP做法，想了半天不会写，还是写了个错的。

毛题，数据有问题，搜索竟然是答案错误。。。

program p1069;

const nmax=800;

var n:longint;

dist:array[1..nmax,1..nmax]of real;

x,y:array[1..nmax]of real;

mark:array[1..nmax]of boolean;

ans,s:real;

procedure init;

var i,j:Longint;

begin

readln(n);

for i:=1 to n do begin

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

for j:=1 to i-1 do

begin

dist:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));

dist[j,i]:=dist;

end;

end;

end;

procedure dfs(now,total:Longint);

var i:Longint;

begin

if total=n then

begin

if s

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

干嘛放在动规啊

居然被我这种菜鸟秒杀PRIM

增加自信。。。。。

……被我做成了初中数学题~~`

这个是动归算法，可惜没过啊！

function work(l,r:integer):real;

var ans:real;

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

begin

if a0 then exit(f[l,r]);

if abs(r-l)=1 then

begin

f[l,r]:=dis[l,r];

exit(f[l,r]);

end;

if r>l then

ans:=min(work(l+1,r)+dis[l,l+1],work(r,l+1)+dis[l,r])

else

ans:=min(work(l-1,r)+dis[l,l-1],work(r,l-1)+dis[l,r]);

f[l,r]:=ans;

exit(ans);

end;

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

样例没有过~交上AC，水。徒增通过题数。

话说这根本不是最小生成树..

原题是ural1143..

应该是求最短哈密顿链才对..

不过对这数据我也实在无语了..

最小生成树=哈密顿回路???

杂可能回得来呢?

求正确解答.

var x,y,c,d,a,b,max,x1,x2:extended;

n,i:longint;

begin

readln(n);c:=0;max:=0;

readln(x,y);x1:=x;x2:=y;

for i:=2 to n do begin

readln(a,b);

d:=sqrt(sqr(x-a)+sqr(y-b));

if maxmax then max:=d;

c:=c+d;

writeln(c-max:0:3);

end.

数据太弱了。。。。。

这样都能过啊！！！！

周长减最大边?

数据给错了。分明是个DP,

最小生成树与周长减最大边显然是错误的。

（最小生成树与哈密顿难道有什么必然联系吗？显然没有啊……）

鉴于数据是错的，就只能用个错误的方法A掉……

第一次知道

原来可以不用过样例的ac哈

....重复点。。。。。prim的弱点。。。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

Prim，周长-最大边 都可以。拿来练习Prim

绝对玩笑，周长-最大边=AC！

这道题绝对是动规，prim和周长减最大边绝对是错误的。之所以能过完全是因为

数据太弱了。

国家集训队2002年何林的论文上有这道题，大家去看一看吧。

不过需要改一改

我恨Lora Temper，同样程序交两次ac

．．．一道经典的DP．．．竟然被搞成prim了．．－　－

最小生成树确实可以得出正确答案，因为树的边都是凸多边形上的边，可证（若走折线，则在X轴与Y轴上有很多来来往往的路径射影，走了很多“冤枉路”）。

多边形周长减去最长边也是对的，证明如上。

原题中并没有规定几个点都在一个凸多边形上，这只是这种笛卡尔平面遍历题的一个特例，最简单的特例。

若吧这道题的数据规模改小点，不加凸多边形限制，就是一道用二进制储存状态的动态规划例题（在哪里看过的我忘了）。