讨论 / 发题解增RP
sser_cgb 2013-11-04 11:57:41
点我顶贴 收藏 删除
const maxn=1000;

maxl=200;

var c:array[1..maxl,1..maxl]of longint;

x:array[0..maxn]of longint;

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

l,n,i,j,k,p,q,pr:longint;

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

begin

if a>b then exit(b)

else exit(a);

end;

begin

readln(l,n);

for i:=1 to l do

begin

for j:=1 to l do read(c[i,j]);

readln;

end;

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

f[1,1,2]:=0; x[0]:=3;

p:=0; q:=1;

for k:=1 to n do

begin

read(x[k]);

for i:=1 to l-1 do

if not(x[k-1]=i) and not(x[k]=i) then

for j:=i+1 to l do

if not(x[k-1]=j) and not(x[k]=j) then

f[p,i,j]:=f[q,i,j]+c[x[k-1],x[k]];

for i:=1 to x[k-1]-1 do f[p,i,x[k-1]]:=2000000000;

for i:=x[k-1]+1 to l do f[p,x[k-1],i]:=2000000000;

for i:=1 to x[k-1]-1 do

if not(i=x[k]) then

begin

for j:=1 to i-1 do

if not(j=x[k-1]) then

f[p,i,x[k-1]]:=min(f[p,i,x[k-1]],f[q,j,i]+c[j,x[k]]);

for j:=i+1 to l do

if not(j=x[k-1]) then

f[p,i,x[k-1]]:=min(f[p,i,x[k-1]],f[q,i,j]+c[j,x[k]]);

end;

for i:=x[k-1]+1 to l do

if not(i=x[k]) then

begin

for j:=1 to i-1 do

if not(j=x[k-1]) then

f[p,x[k-1],i]:=min(f[p,x[k-1],i],f[q,j,i]+c[j,x[k]]);

for j:=i+1 to l do

if not(j=x[k-1]) then

f[p,x[k-1],i]:=min(f[p,x[k-1],i],f[q,i,j]+c[j,x[k]]);

end;

p:=p xor 1;

q:=q xor 1;

end;

pr:=maxlongint;

for i:=1 to l-1 do

if i<>x[k] then

for j:=i+1 to l do

if j<>x[k] then pr:=min(pr,f[q,i,j]);

writeln(pr);

end.

#1 lvchaojie@2013-11-04 15:01:56
回复 删除
这是题解吗?这不是ac代码吗?

#2 sser_cgb@2013-11-04 17:41:11
回复 删除
本题可以较容易想出dp方程

f[k,i,j,x[i]]=min(f[k-1,i,j]+c[x[i-1],x[i]])

f[k,i,x[i-1],x[i]]=min(f[k-1,i,j]+c[j,x[i]])

其中:

1.k表示步数,x[i]数组表示i步的位置

2.f数组中三个变量表示第i步时三个员工位置,根据“同一时刻不可以有多个人在同一地点”,需保证三个变量值不相等

复杂度为n*l^3

====完美的分割线====

1.第i步时三个员工位置必包括x[i],所以可降为两维

2.dp方程无后效性,可用滚动数组

3.第i步时两个员工的位置如(1,3)(3,1)会导致运算重复,我们可以使f[k,i,j]中i<j,减少1/2的运算量

4.注意初始化,本题的初始化和"f[i,j,k]三个变量值不相等"判断较难写,代码的初始化堪称完美,可参考学习

复杂度n*l^3/2 空间l^2*2,完美过100%数据

难度:noip提高组第二题

类型:典型的dp降维优化问题

#3 120133@2013-11-04 20:00:47
回复 删除
额,那个用队列,一个元素存3个量,分别表示3个农民的位置,再判断当前是否可行...宽搜解决?

又因为3个农民都是不可以位置重复,则a,b,c三个量总是单调的,则若一个时刻需求服务位置就最多只有两种决策

再随便剪一下枝...好像都不用这么复杂吧...

#4 sser_cgb@2013-11-04 20:02:54
回复 删除
回复 #3 120133:的确可以,数据是弱的
查看更多回复
提交回复