什么?搜索是0ms,不敢相信,刚开始写了个笨蛋搜索才5分,添一个参数就是100啦~~~

双向广搜25分……

其它点全部0s...为什么第10个点就错呢?

有什么特别么?

楼下的:我用深搜都50了...

请问随机化是如何秒杀的？愿闻详解，我一直是45.

lemon_cn的剪枝代码中x数组是做什么用的？

“然后在搜索排列树的时候将搜索的那一层之后的所有人的最小值累加”

搜索的那一层之后的所有人的最小值，是什么意思？

我按我的理解添加了代码，的确快了很多，但是当n=11时仍然超时，何解？

编译通过...

├ 测试数据 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：答案正确... 25ms

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

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

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

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

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

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

状态压缩- -，比赛时的程序。。比较猥琐0_0

状态压缩DP

f 表示 在j这个状态下 当前传到i时最小代价 利用位运算

效率为 n*2^n

状压DP或者spfa吧

向ＬＳ的ＬＳ大牛致敬

贪心估界，最优化剪枝，卡时，80分。

谁告诉我再怎么优化？

多谢大牛指点！

终于0ms了

状态压缩DP

30行程序秒杀

至于搜索0ms的。。只能说是数据弱。。

无语,一个明显不能AC的掐时,AC了.......

使用类似最小生成树的方法

得到了80分

还有几个过不去了

回溯法（25分）：

const maxn=2147483647;

var a,v:array[1..16,1..16] of longint;

n,min,val,i:longint;

procedure init;

var i,j:longint;

begin

readln(n);

for i:=1 to n do begin

for j:=1 to n do read(a);

readln;

end;

min:=maxn;

val:=0;

end;

procedure work(x,p:longint);

var i:longint;

begin

if x=n then

if val

随机化，全0ms啊，哈哈

唉..做题的时候看N= 16我也就没继续想,以为写个DFS就可以了..没想到只得了45分,过后想想,本来我也用位运算处理了,再写成 记忆化搜索也不麻烦 ..唉..

再写一次,一下AC..郁闷 ..

昨天用DP做忘记记忆个东西，导致了某个点可以重复选，结果只有80分，可见测试数据之弱.

用我的方法得80分的请注意,一定要记录每个状态所包括的所有结点,可以用数组也可以用位运算进行记录

阶段（I）：长度

状态（I，J1，J2）：长度为I，以J1为起点，J2为终点的最小值

决策（K）

所以，DP方程如下：

F:=Min{F+Map[K,J2],F+Map[J1,K]}

初始化F[1,J1,J1]:=0; F[2,J1,J2]:=Map[J1,J2];其他F值为Maxlongint

不过，为了不重复选择某个点，我们需要另开一个表，储存当前状态选用了哪些点。这样在决策的时候，还需要判断选用此决策是否重复加入了某个点。

虽然是（N*N*N*N*N），但是N是很小的，所以0ms秒杀（用位运算实现集合可以降低一维的循环）。想的有点复杂，如果N大了，绝对超时，此方法仅限过此题。

编译通过...├ 测试数据 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

help!!!!!!70分

有个点T了

var

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

f:Array[0..16,0..65535]of longint;

i,j,k,p,n:longint;

h:array[0..16]of longint;

procedure dfs(node,state:longint);

var

i:integer;

begin

for i:=1 to n do

if state and h[i]=h[i] then

begin

if f=2038004089 then dfs(i,state-h[i]);

if f[node,state]>f+a then

f[node,state]:=f+a;

end;

end;

begin

readln(n);

h[1]:=1;

for i:=2 to n do

h[i]:=h shl 1;

for i:=1 to n do

for j:=1 to n do

read(a);

fillchar(f,sizeof(f),$79);

for i:=1 to n do

f:=0;

dfs(0,h[n]*2-1);

writeln(f[0,h[n]*2-1]);

end.

怎么剪支

为什么随机算法.老是错啊 而且是惊人相似的错误！

DFS+剪枝就可以0msAC了.

剪枝如下：

把每一个人能传出的最小值记录一下

然后在搜索排列树的时候将搜索的那一层之后的所有人的最小值累加

加上已经传出的值

若它已经大于目前最小值就剪掉.

core code:

//code:1

for(int i=0;ic[i][j];

if(mins[i]>c[i][j]&&c[i][j]>=0)mins[i]=c[i][j];

}//记录mins数组，就是每个人传出的最小值

//code:2

void dfs(int layer)

{

if(layer==n)

{

if(ccost