编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

直接用mst过了。

数据太弱了？

周长-最大边，错！prim，错！dp不会。。。怎么办哟

说一下现在的状况：

相信dp，mst有反例，数据没有问题但是题目描述不正确，可以从任意一点开始（不过题目也没说第一个点是哪个点），一开始没考虑，交了n多次只有50分

其实和从一个点开始也差不了多少，只是初始化不同而已，抱着自虐的心态交了一次......竟然ac了

prim是错的。。

是DP。

题解 http://254117343.blog.163.com/

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

├ 测试数据 01：运行超时|无输出...

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

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

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

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

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

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

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

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

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

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

Unaccepted 有效得分：90 有效耗时：3644ms

三次提交了同样的程序 只是改变了数组的大小，结果是如此ASTONISHING,的超级郁闷。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

kruscal写出9ms来了..欢迎大家鄙视我

题目是 凸多边形...............什么方法也一样...............

希望大牛可以详细解释下方程

lx 的方程是错误的。

MST绝对是错误的。

周长减去最长边很容易想到反例的。

So 数据太弱了~

贴个方程

f:=min(f+d,f+d);

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

很简单的

1表示在左边i点 0表示在右边j点

可以证明,路径不能交差

所以DP就很明朗了.时间是O(n^2)

这样写好程序交上去后是10分

后来才发现,题目的描述根本不对.

测试数据是可以从任意一点开始的,而不是只大门.

枚举的话时间是O(n^3)就明显不够了.

所以只要把点拉成2n个然后DP找状态即可降为O(n^2)

我没用循环而是用的记忆化递归,所以慢了点.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

DP秒杀，和关路灯类似，走到左边这个点最短路，还是走到右边这个点最短路，

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

没有秒杀不过很不错...

但是也很遗憾..因为是照搬下面大牛的动规方程...

提供以下代码

//---|-

program s1069;

var

i,j,k,n:longint;

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

f:array[0..1800,0..1800,0..1] of real;

ans:real;

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

begin

i:=i mod n; j:=j mod n;

if i=0 then i:=n; if j=0 then j:=n;

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

end;

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

begin

if a=0 then exit(b); if b=0 then exit(a);

if a>b then exit(b)

else exit(a);

end;

begin

fillchar(f,sizeof(f),0);

ans:=maxlongint;

read(n);

for i:=1 to n do

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

for k:=1 to n-1 do

for i:=1 to 2*n-1-k do

begin

j:=i+k;

f:=min(f+dis(i,j),f+dis(i,i+1));

f:=min(f+dis(j,j-1),f+dis(i,j));

end;

for i:=1 to n do ans:=min(min(f,f),ans);

writeln(ans:0:3);

end.

//---|---|---|

f:=min(f+dis(i,j),f+dis(i,i+1));

f:=min(f+dis(j,j-1),f+dis(i,j));

//---|---|---|

这题第一个点不是起点阿,被恶搞了,出题的有点不负责任阿

ws 是什么？

黑书 又是什么？

理论上PRIM绝对是错的，还是老实点DP，虽然我不是很会.

谁给个DP式子，顺便解释下。

因为所有点正好组成了一个凸多边形；

所以生成树算法生成的一定是一条合法的路线。

还楞着干啥？Prim啊！

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

没有秒杀

用dp,但程序比较ws，用了35行，主要是要处理起点不一定是1这个事情

主要参看了黑书，虽然以前看的时候没怎么看懂，不过编一编就懂了

一个很重要的思想就是路径不能交叉，个人的解释是三角形两边之和大于第三边，即四边形中对角线交点和两个端点所组成的三角形中，属于对角线的两条边之和大于第三边。

所以只能走不交叉的路，转移的费用就只需要O(1)了

prim我不知道对不对，能ac的话很奇怪……

好WS....

DP

为什么我的什么慢。。。。。。。

prime可能所有的点不是只走了一遍，所以会错。错误图论算法。用DP，更正确。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

图，0MS过（用prim 过了）

经典名言：

“prim （好写），kruscal （好理解）”

————著名中山市纪念中学大牛_冯艺

。。。。。。（虽然我只懂prim ）。。。。。。。。。。。。。。。。

用prim ,爽！！！^_^