64 条题解
-
0
new world LV 10 @ 2009-10-01 22:20:28
三维的顺推
c表示三辆车分别走到的城市i,j,k时的最优解
l=max(i,j,k)+1,则
c[l,j,k]=min(c[l,j,k],c+d);
c=min(c,c+d[j,l]);
c=min(c,c+d[k,l]);
当l=n时更新最优解ans -
0
var a:array[1..100,1..100]of integer;
car:array[1..100]of integer; n:integer;procedure re;
var i,j:integer;
begin
readln(n);
fillchar(a,sizeof(a),0);
for i:=1 to n-1 do
begin
for j:=i+1 to n do read(a);
readln;
end;
fillchar(car,sizeof(car),0);
car[1]:=3;
end;procedure solve;
var i,j,min,k,w:integer;
begin
w:=0;
for i:=2 to n do
begin
min:=30000;
for j:=1 to i-1 do if car[j]>0 then
if min>a[j,i] then begin min:=a[j,i]; k:=j; end;
car[k]:=car[k]-1; car[i]:=car[i]+1; w:=w+min;
end;
writeln(w);
end;begin
re;
solve;
end. -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
赤裸裸的一次AC
暴汗ing...
首先说：这题很水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水水
，水到我们学校有一个资料是有写它的——《DP专题》。。。
记忆化搜索啊啊啊啊啊啊！！！！三维的记忆化搜索。。。。
即便是这样，我还是救护车（220）个AC的。。。
这么水的题都没什么人做，暴汗啊啊啊啊啊啊！！！！！
http://lifeich1.spaces.live.com/blog/cns!9AB465A9D807BE22!127.entry
这是我的程序。。。 -
0
如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/35722312_d.html
-
0
支持Dev的！形象，妙。但是如何保证递推过程中个城市已经访问，还是有点疑惑。
Program vijos_1547;
Var
n,i,j,k,min:longint;
a:array[0..101,0..101]of longint;
v:array[0..101]of longint;
f:array[0..101]of longint;
Begin
readln(n);
for i:=1 to n-1 do
for j:=i+1 to n do
begin
read(a);
a[j,i]:=a;
end;
fillchar(f,sizeof(f),0);
fillchar(v,sizeof(v),0);
v[1]:=3;
for i:=2 to n do
begin
min:=maxlongint;
k:=0;
for j:=1 to i-1 do
if (a0)and(a0) then
begin
min:=a;
k:=j;
end;
dec(v[k]);
inc(v[i]);
f[i]:=f+min;{注意是f，而不是我们常用的f[k]}
end;
writeln(f[n]);
End.
new world
LV 10
@ 2009-10-01 22:20:28
