讨论 / 60分,pascal。求解释,好像也是超时出现219,记忆化搜索
Fish、のTorres 2011-08-16 07:00:00
点我顶贴 收藏 删除
var a,f:array[1..1000,1..1000]of longint;

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

i,j,n,x,r:longint;

function dfs(m,t:longint):longint;

var min,s,i,w:longint;

begin

if t=0 then exit(c[m]);

if f[m,t]<>0 then exit(f[m,t]);

min:=maxlongint;

for i:=1 to n do begin

if i<>m then begin

s:=dfs(i,t-1)+a[m,i];

if s<min then min:=s;

end;

end;

f[m,t]:=min;

exit(min);

end;

begin

readln(n);

for i:=1 to n do read(b[i]);

for i:=1 to n do read(c[i]);

for i:=1 to n do

for j:=1 to n do read(a[i,j]);

x:=maxlongint;

for i:=1 to n do begin

r:=dfs(i,6)+b[i];

if r<x then x:=r;

end;

write(x);

end.

#1 逍遥游侠@2011-08-08 05:43:00
回复 删除
60分,DP,一个超时三个219

program caihong;

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

n,i,j,k:integer;

min:longint;

ds,de:array[0..1001] of integer;

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

begin read(n);

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

fillchar(ds,sizeof(ds),0);

fillchar(de,sizeof(de),0);

for i:=1 to n do

begin

read(ds[i]);

f[1,i]:=ds[i];

f[0,i]:=ds[i];

end;

for i:=1 to n do read(de[i]);

for i:=1 to n do for j:=1 to n do

read(a[i,j]);

for i:=2 to 7 do

for j:=1 to n do

begin

min:=maxlongint;

for k:=1 to n do

if k<>j then

begin

if f[i-1,k]+a[k,j]<min then

min:=f[i-1,k]+a[k,j];

end;

f[i,j]:=min;

end;

min:=maxlongint;

for i:=1 to n do

if f[7,i]+de[i]<min then min:=f[7,i]+de[i];

write(min);

end.

#2 lxl@2011-08-12 03:58:00
回复 删除
此题pascal过不去

RT,数据量应该太大

而且RQ的评测机有问题,一个超时接下来3个点错误

这两个程序是正确的

#3 Fish、のTorres@2011-08-16 07:00:00
回复 删除
有一种想写个c语言能ac的程序

再用pascal打表- -

查看更多回复
提交回复