我的错误程序，意外85？！

意想不到的剪枝。。

竟然OMS AC了。。。

编译通过...├ 测试数据 01：答案正确... 0ms├ 测试数据 02：答案正确... 0ms├ 测试数据 03：答案正确... 0ms├ 测试数据 04：答案正确... 0ms├ 测试数据 05：答案正确... 0ms├ 测试数据 06：答案正确... 0ms├ 测试数据 07：答案正确... 0ms├ 测试数据 08：答案正确... 0ms├ 测试数据 09：答案正确... 0ms├ 测试数据 10：答案正确... 0ms├ 测试数据 11：答案正确... 0ms├ 测试数据 12：答案正确... 0ms├ 测试数据 13：答案正确... 0ms├ 测试数据 14：答案正确... 0ms├ 测试数据 15：答案正确... 0ms├ 测试数据 16：答案正确... 0ms├ 测试数据 17：答案正确... 0ms├ 测试数据 18：答案正确... 0ms├ 测试数据 19：答案正确... 0ms├ 测试数据 20：答案正确... 0ms-------------------------Accepted 有效得分：100 有效耗时：0ms哎!随机化才是王道!

好,我来讲一下这道题的解法.这题可以用DP做,也可以用DFS做.我没想到好的DP方法,是用DFS过的,不过也是全0S. 因为这题的任一个方案都是一个全排列,因此可以对朴素的搜索进行一个小小的优化,即搜索排列树:说说是排列树,其实也就是全排列的一种,可以较快的得出所有全排列,伪代码可以带百度上搜. 用排列树剪除了大部分的亢余搜索,使程序尝试复杂度从N^N 降至N! 再加上一个计算估价剪枝,0S轻松.所谓计算估价剪枝就是最优化剪枝的一种:当前的费用+未到接点所需最小费用>MIN,就退出.我想这一步,楼下的牛都说过了..说实话,排列树是个好东西

我同学和楼下一样，不知道楼下转移方程是什么。

状态压缩dp，O（2^n*n^2），这个貌似是传说中的不要求回路的邮差问题，是NP问题吧，但是n只有16，所以可以。至于有人用搜的而且更快，我只能Orz了。。。但是我只有95分，还没不知道倒数第二个点有什么特殊之处。。。

新：倒数第二个点是数据范围问题，把程序中所有变量都开longint就可以了。。。以后我一定能用Longint就用longint。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

├ 测试数据 13：答案正确... 181ms

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

├ 测试数据 15：答案正确... 572ms

├ 测试数据 16：答案正确... 572ms

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

├ 测试数据 18：答案正确... 572ms

├ 测试数据 19：答案正确... 572ms

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

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

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

DFS

用最小生成树得不到正确解，但可以得到一个相当近似的解

“用搜索会比标准答案还少一些”：遍历过所的点，但这些点不一定连成链

位运算?- -

用位运算+最优性剪枝可以全部0msAC.

谁告诉我,为什么我用搜索会比标准答案还少一些......

我用n个最小生成树，以最小值为解，结果只有90

郁闷中，谁能告诉我这个方法哪里出错了吗？

理论上来说这题用最小生成树是要0分的,80分,90分只不过是运气好,数据弱吧.

我用的是最小生成树，但只有90

为什么prim只有80分？

LV.唱响 ,我用你的算法写了一下只有80分请帮我看看

var

f:Array[1..16,1..16,1..16]of longint;

g:Array[1..16,1..16,1..16,1..16]of boolean;

a:Array[1..16,1..16]of longint;

i,j,k,l,n,best:longint;

function min(x,y:longint):longint;

begin

if x

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

朴素dfs+贪心剪枝

非dp秒杀。。

1.先贪心出较优解min。搜索大于min就退，小于min就更新

2.之间用m[k]表示到k点的所有路径中的最小值(预处理），如果未到的点中的sum(m)+当前代价>min，就退

终于AC了，dfs+qsort确定搜索顺序+最优化剪枝+卡时

最小生成树....prime....krus***|*过80..

n个最小生成树吧