位运算学的太弱了……

DP都没有秒杀……

编译通过...

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

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

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

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

做了将近一年...

WS贪心+最优化剪枝+估价剪枝+卡时间剪枝终于过了...汗死

不想写排列树的同学看这里:http://hi.baidu.com/sk_raucous/blog/item/9d7b578a0674a9769f2fb44c.html

n个prim最小生成树80分。

用二进制方法表示状态

p表示j状态是传到i的最小值

则有状态转移方程。

p:=max{p[k,j-a[k]]+map[k,i]};

其中a[k]:=2^k-1;

例如此时1、2、4已经穿过。并且此时传到2；那么用p[2,11]可以表示

11=8+2+1；

#include

#include

#define maxn 16

#define INF 20000000

#define Ith(i) (1

感谢pzy3303大牛

编译通过...

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

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

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

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

看看我的怎样才能完全AC？

var

a:array[0..16,0..16] of longint;

f:array[0..16,0..16] of longint;

n: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;

end;

procedure main;

var i,j,k:longint;ans:longint;

begin

for i:=2 to n do

for j :=1 to n do

begin

f:=maxlongint;

for k:=1 to n do

if (a[k,j]-1) and (f+a[k,j]

二进制动态规划。

使用real还是要注意精度，加0.0000000001；

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

随机化是王道！

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

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

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

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

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

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

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

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

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

├ 测试数据 11：运行超时...

├ 测试数据 12：运行超时...

├ 测试数据 13：运行超时...

├ 测试数据 14：运行超时...

├ 测试数据 15：运行超时...

├ 测试数据 16：运行超时...

├ 测试数据 17：运行超时...

├ 测试数据 18：运行超时...

├ 测试数据 19：运行超时...

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

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

Unaccepted 有效得分：45 有效耗时：338ms

没加减枝的结局

DFS+最优化剪枝

编译通过...

├ 测试数据 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

1.5小时鏖战，11次提交，疯狂剪枝……

用最小生成树+dfs只能45分，

加上超强剪枝就0ms过啦！

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

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

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

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

这题数据太弱了。。我只加了一个最基本的最优性剪枝就0sAC了。。意义不大。。

编译通过...

├ 测试数据 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

编译通过...

├ 测试数据 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

剪枝剪得好辛苦…………

感谢楼下lemon_cn大牛～～

楼下的大牛指导一下啊，为什么随机化撑死只有70分啊.......

var

n,i,j,k,l,num,min:longint;

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

b:array[1..16] of boolean;

begin

randomize;

readln(n);

for i:=1 to n do

for j:=1 to n do

read(a);

min:=maxlongint;

repeat

inc(j);

fillchar(b,sizeof(b),false);

num:=0;

l:=0;

for k:=1 to n-1 do

begin

repeat

i:=random(n)+1;

until b[i]=false;

b[i]:=true;

if l=0

then l:=i

else begin

num:=num+a[l,i];

l:=i;

end;

end;

for k:=1 to n do

if b[k]=false

then begin

num:=num+a[l,k];

break;

end;

if num

提交了n多次,终于不TLE了

参考的楼下lemon_cn和voyagec2的题解

对排列树还不是很明白,baidu和google上关于排列树的好的资料也没找到

不过看了lemon_cn的代码,受到了些启发

编译通过...

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

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

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

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

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

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

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

提交了n多次，可总是超时……

当我看了楼下lemon_cn的剪枝，终于知道如何降低时间复杂度了！

太感谢，我又学到许多，太开心了！

program pass;

var

n:integer;

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

num:array[0..65535] of integer;

w:array[1..16,1..16] of integer;

a,h:array[0..16] of integer;

// ma:longint;

procedure init;

var

i,j:integer;

begin

read(n);

for i:=1 to n do

for j:=1 to n do

read(w);

end;

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

begin

if a>b then min:=b

else min:=a;

end;

procedure work;

var

i,j,k:integer;

t,ma:longint;

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

begin

m[0]:=1;

for i:=1 to n do

m[i]:=m*2;

for i:=1 to n do

num[m]:=i;

for i:=1 to m[n]-1 do

for j:=1 to n do

f:=maxlongint;

for i:=1 to n do

f[m,num[m]]:=0;

for i:=1 to m[n]-1 do

begin

t:=i;

for j:=1 to n do

begin a[j]:=t mod 2;t:=t div 2;end;

for j:=1 to n do

for k:=1 to n do

if (a[j]=1)and(a[k]=1)and(jk) then

if f[i-m[j-1],k]maxlongint then

f:=min(f,f[i-m[j-1],k]+w[k,j]);

end;

ma:=maxlongint;

for i:=1 to n do

ma:=min(ma,f[m[n]-1,i]);

{ for i:=1 to m[n]-1 do

begin

for j:=1 to n do

write(f,' ');

writeln;

end;

} write(ma);

end;

begin

assign(input,'pass.in');

assign(output,'pass.out');

reset(input);rewrite(output);

init;

work;

close(input);close(output);

end.

这个是70的程序,复杂度2^n*n*n,用的DP,为什么把所用的integer改成longint就AC?貌似我用integer的地方没有超过integer的范围啊.........

记忆化搜索

program p1456_1;var n,i,j,k:integer; max,ans:longint; f,g:array[0..65536,0..16]of longint; a:array[0..16,0..16]of longint;function work(k:longint;p:integer):longint;var i:integer; kk:longint;begin if f[k,p]0)and(work(k,i)+a