讨论 / 依旧记忆化搜索 不懂的进(WXT专用题解)
w7x7t772007 2012-08-15 02:20:00
点我顶贴 收藏 删除
先代码 再解释

第一次提交 AC 90 第7个点没过 原因大家都知道 那数据的 答案是0 容易让人陷入死循环

第2次 该了之后 就A了 原因下面会具体介绍

VAR

f:array[0..30,0..30] of longint;F数组F[I,J]表示经过J次传到I手里的总方案

i,j,n,m:longint;

procedure mdfs(x,y:longint);还是我的风格 用过程做记忆化搜索

var

x1,y1:longint;

begin

if f[x,y]<>-1 then exit;如果是-1 就表示没有得出局部最优结果 那么继续算

注意(很大的问题) 原来 我初始化不是-1 而是0 结果就第7个点没过

事实上 这个0有2种含义 第1:表示没得出结果 要继续算 第2:结果确确实实是0 但是一个值不能表示2个含义啊 计算机就以为 凡是0就继续算 以至于结果就是0的数据 就 死循环了。 该了-1就AC了

if (x=1)and(y=0) then

begin

f[x,y]:=1; 这个 也很重要 F[1,0]=1 表示 初始边界 意思是 一个人 也就是小明 传0次球(注意 就等于没穿 拿在手上)那么这也是一种方案

我们按照题意来看 当然是不符合的 但是 实际上为了程序的运行和人为理解 也是可行的 那么这样以来方程就很容易得出了。

exit;

end;

if y=0 then

begin

f[x,y]:=0;这里是0 因为0次的时候球在小明那里 其他人的方案数必须是0

exit;

end;

if x=n then x1:=1 else x1:=x+1;X1表示右边的人的位置 并且处理了边界

if x=1 then y1:=n else y1:=x-1;同上 Y1表示左边

mdfs(x1,y-1);得出F[X1,Y-1] 具体含义已经解释

mdfs(y1,y-1);

if x1<>y1 then

f[x,y]:=f[x1,y-1]+f[y1,y-1] else f[x,y]:=f[x1,y-1];

这里也是个重点。

一开始调试的时候没加 后来发现是这样一回事 当左边右边是同1个人的时候 就必须 去掉重复计算的 (也就是N=2)的时候。

end;

begin

readln(n,m);

for i:=0 to n do

for j:=0 to m do

f[i,j]:=-1; 初始化 这里可以 1 开始的 但是我就懒的优化了

mdfs(1,m);

writeln(f[1,m]);

end.

希望支持 打字也累啊

^^^^wxt^w^x^t^wxt^^^^

#1 rqnoj外用@2016-05-21 16:51:02
回复 删除
赞^-^
查看更多回复
提交回复