讨论 / 【后面超时啊】。。。
汪小正 2011-10-06 21:25:00
点我顶贴 收藏 删除
写了个DP 时间复杂度是O(t*n*16^3)。

貌似被卡常数了?

还是DP可以优化?

program p644;

var

k,tot,x,b,c,minn,i,j,n,t:longint;

a1,a2,a3:array[0..17,0..17]of longint;

time,w:array[0..1001]of longint;

f:array[0..1001,0..17,0..17,0..17]of longint;

procedure init;

begin

assign(input,'p644.in');

reset(input);

assign(output,'p644.out');

rewrite(output);

end;

procedure outit;

begin

close(input);

close(output);

end;

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

begin

if a<b then exit(a);

exit(b);

end;

procedure qsort(l,r:longint);

var

i,j,x,t:longint;

begin

i:=l; j:=r; x:=time[(l+r)div 2];

repeat

while time[i]<x do inc(i);

while time[j]>x do dec(j);

if not(i>j) then

begin

t:=time[i]; time[i]:=time[j]; time[j]:=t;

t:=w[i]; w[i]:=w[j]; w[j]:=t;

inc(i); dec(j);

end;

until i>j;

if i<r then qsort(i,r);

if l<j then qsort(l,j);

end;

procedure main;

begin

readln(n);

for i:=1 to n do readln(time[i],w[i]);

qsort(1,n);

for i:=1 to 16 do

for j:=1 to 16 do read(a1[i,j]);

for i:=1 to 16 do

for j:=1 to 16 do read(a2[i,j]);

for i:=1 to 16 do

for j:=1 to 16 do read(a3[i,j]);

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

f[0,1,1,1]:=0;

for i:=1 to n do

for b:=1 to 16 do

for c:=1 to 16 do

for x:=1 to 16 do

begin

f[i,w[i],b,c]:=min(f[i,w[i],b,c],f[i-1,x,b,c]+a1[x,w[i]]);

f[i,b,w[i],c]:=min(f[i,b,w[i],c],f[i-1,b,x,c]+a2[x,w[i]]);

f[i,c,b,w[i]]:=min(f[i,c,b,w[i]],f[i-1,c,b,x]+a3[x,w[i]]);

end;

minn:=maxlongint;

for b:=1 to 16 do

for c:=1 to 16 do minn:=min(minn,f[n,w[n],b,c]);

for b:=1 to 16 do

for c:=1 to 16 do minn:=min(minn,f[n,b,w[n],c]);

for b:=1 to 16 do

for c:=1 to 16 do minn:=min(minn,f[n,c,b,w[n]]);

writeln(minn);

end;

begin

init;

readln(tot);

for k:=1 to tot do main;

outit;

end.

#1 slzxqjh@2011-09-27 20:57:00
回复 删除
我的比你简单多了,不超时但216啊。
#2 slzxqjh@2011-09-27 21:38:00
回复 删除
终~~~于过了。

得分: 100分 [我要评价一下题目~]

提交日期: 2011-9-27 21:37:00

有效耗时: 3484毫秒

测试结果1: 通过本测试点|有效耗时297ms

测试结果2: 通过本测试点|有效耗时250ms

测试结果3: 通过本测试点|有效耗时234ms

测试结果4: 通过本测试点|有效耗时266ms

测试结果5: 通过本测试点|有效耗时297ms

测试结果6: 通过本测试点|有效耗时328ms

测试结果7: 通过本测试点|有效耗时437ms

测试结果8: 通过本测试点|有效耗时500ms

测试结果9: 通过本测试点|有效耗时438ms

测试结果10: 通过本测试点|有效耗时437ms

提交代码: view sourceprint?01.var i,j,k,l,n,t,q,max:longint;

02.

d:array[1..1000,1..16,1..16,1..16]of longint;

03.

a,b:array[1..1000]of longint;

04.

f1,f2,f3:array[1..16,1..16]of integer;

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

06.begin

07.if a<b then exit(a)

08.

else exit(b);

09.end;

10.procedure kp(l,r:longint);

11.var

12.

ii,jj,kk,nn,mm,tt:longint;

13.begin

14.

ii:=l;

15.

jj:=r;

16.

nn:=(l+r) div 2;

17.

mm:=a[nn];

18.

while ii<jj do

19.

begin

20.

while a[ii]<mm do inc(ii);

21.

while a[jj]>mm do dec(jj);

22.

if ii<=jj then

23.

begin

24.

tt:=a[ii];

25.

a[ii]:=a[jj];

26.

a[jj]:=tt;

27.

tt:=b[ii];

28.

b[ii]:=b[jj];

29.

b[jj]:=tt;

30.

inc(ii);

31.

dec(jj);

32.

end;

33.

end;

34.

if jj>l then kp(l,jj);

35.

if ii<r then kp(ii,r);

36.end;

37.begin

38.readln(t);

39.for q:=1 to t do begin

40.readln(n);

41.for i:=1 to n do

42.readln(a[i],b[i]);

43.kp(1,n);

44.for i:=1 to 16 do

45.for j:=1 to 16 do

46.read(f1[i,j]);

47.for i:=1 to 16 do

48.for j:=1 to 16 do

49.read(f2[i,j]);

50.for i:=1 to 16 do

51.for j:=1 to 16 do

52.read(f3[i,j]);

53.filldword(d,sizeof(d)div 4,maxlongint div 2);

54.d[1,b[1],1,1]:=f1[1,b[1]];

55.d[1,1,b[1],1]:=f2[1,b[1]];

56.d[1,1,1,b[1]]:=f3[1,b[1]];

57.for i:=2 to n do

58.for j:=1 to 16 do

59.for k:=1 to 16 do begin

60.d[i,b[i],j,k]:=min(d[i,b[i],j,k],d[i-1,b[i-1],j,k]+f1[b[i-1],b[i]]);

61.d[i,j,b[i],k]:=min(d[i,j,b[i],k],d[i-1,j,b[i-1],k]+f2[b[i-1],b[i]]);

62.d[i,j,k,b[i]]:=min(d[i,j,k,b[i]],d[i-1,j,k,b[i-1]]+f3[b[i-1],b[i]]);

63.d[i,b[i],b[i-1],k]:=min(d[i,b[i],b[i-1],k],d[i-1,j,b[i-1],k]+f1[j,b[i]]);

64.d[i,b[i],k,b[i-1]]:=min(d[i,b[i],k,b[i-1]],d[i-1,j,k,b[i-1]]+f1[j,b[i]]);

65.d[i,j,b[i],b[i-1]]:=min(d[i,j,b[i],b[i-1]],d[i-1,j,k,b[i-1]]+f2[k,b[i]]);

66.d[i,b[i-1],b[i],k]:=min(d[i,b[i-1],b[i],k],d[i-1,b[i-1],j,k]+f2[j,b[i]]);

67.d[i,j,b[i-1],b[i]]:=min(d[i,j,b[i-1],b[i]],d[i-1,j,b[i-1],k]+f3[k,b[i]]);

68.d[i,b[i-1],j,b[i]]:=min(d[i,b[i-1],j,b[i]],d[i-1,b[i-1],j,k]+f3[k,b[i]]);

69.end;

70.max:=maxlongint;

71.for j:=1 to 16 do

72.for k:=1 to 16 do begin

73.if d[n,j,k,b[n]]<max then max:=d[n,j,k,b[n]];

74.if d[n,j,b[n],k]<max then max:=d[n,j,b[n],k];

75.if d[n,b[n],j,k]<max then max:=d[n,b[n],j,k];

76.end;

77.writeln(max);

78.end;

79.end.

#3 wilyin@2011-10-01 15:58:00
回复 删除
一开始清零F超时了...注释了就能过了...

不过我写的是记忆化搜索...只要清对应BOOL数组就行了...

#4 luanshaotong@2011-10-02 17:41:00
回复 删除
t*n*16^2 无压力= =
#5 noipyubin@2011-10-06 21:24:00
回复 删除
我的也是N*T*16^3,全部A了,可能你的算法需要一些小的优化,你可以试试不要用MIN函数
#6 noipyubin@2011-10-06 21:25:00
回复 删除
而且答案不用再重新找一边了,DP中可以记录下来直接输出
查看更多回复
提交回复