晴天小猪历险记之Hill

晴天小猪历险记之Hill

最原始的方程就是三角形那个，但是在此基础上还需要一些改进。。1.DP有环怎么办? 别急,先别想着放弃DP,有时候环是可以避免的.这里在每一行中为避免相邻两格左右移动产生的环,可以先推向左的,再推向右的,而同向移动产生的那个“大”环就麻烦一点.其实有个很简单的窍门:先记录从下一行转移来的最优值,然后在本行中寻找代价最小的点,以这个点为起点分别向左向右推,因为最小的点显然是不需要从两侧的点过来的.这样就没有后效性了..2.递推的顺序:递推有两种顺序,可以根据当前状态值推出所有可能的后继状态,也可以根据所有当前状态可能的前驱来推当前值,很多时候,当问题的状态比较有规律时,这两种方法是不相上下的.但是其他情况下一不小心就可能搞错.比如这题题目告诉我们的是从一个状态可行的所有走法(共四种),所以根据这个顺序去编是最保险的。因为这里一个状态的前驱不一定只是四个,边缘的点是特例,可能会有5个来源,所以DP的时候不要随便换状态转移顺序.3.坐标的处理我第一次把上一行的坐标全部向左移了一格..改过来之后还是错,结果发现是又漏了一个%length...在处理滚动数组的时候一定要记得检查每个下标,是不是少了取余运算! 附程序:program v1006;var a,f:array[1..1000,1..1001]of longint; n,i,j,k,minj,mi:longint;function min(a,b,c:longint):longint; begin min:=a; if min>b then min:=b; if min>c then min:=c; end;procedure scan; begin for j:=minj+1 to i do if f[i,j]>f[i,j-1]+a[i,j] then f[i,j]:=f[i,j-1]+a[i,j]; if f[i,1]>f[i,i]+a[i,1] then f[i,1]:=f[i,i]+a[i,1]; for j:=2 to minj-1 do if f[i,j]>f[i,j-1]+a[i,j] then f[i,j]:=f[i,j-1]+a[i,j]; for j:=minj-1 downto 1 do if f[i,j]>f[i,j+1]+a[i,j] then f[i,j]:=f[i,j+1]+a[i,j]; if f[i,i]>f[i,1]+a[i,i] then f[i,i]:=f[i,1]+a[i,i]; for j:=i-1 downto minj+1 do if f[i,j]>f[i,j+1]+a[i,j] then f[i,j]:=f[i,j+1]+a[i,j]; end;begin readln(n); for i:=1 to n do for j:=1 to i do begin read(a[i,j]);a[i,j+i]:=a[i,j]; end; f[n,1]:=a[n,1]; for j:=2 to n do f[n,j]:=f[n,j-1]+a[n,j]; if f[n,n]>f[n,1]+a[n,n] then f[n,n]:=f[n,1]+a[n,n]; for j:=n-1 downto 2 do if f[n,j]>f[n,j+1]+a[n,j] then f[n,j]:=f[n,j+1]+a[n,j]; for i:=n-1 downto 1 do begin f[i,1]:=min(f[i+1,1],f[i+1,2],f[i+1,i+1])+a[i,1]; f[i,i]:=min(f[i+1,i],f[i+1,i+1],f[i+1,1])+a[i,i]; for j:=2 to i-1 do if f[i+1,j]<=f[i+1,j+1] then f[i,j]:=a[i,j]+f[i+1,j] else f[i,j]:=a[i,j]+f[i+1,j+1]; minj:=0;mi:=maxlongint; for j:=1 to i do if mi>f[i,j] then begin minj:=j;mi:=f[i,j]; end; if i>1 then scan; end; {for i:=1 to n do begin for j:=1 to i do write(f[i,j]:3); writeln; end; for i:=1 to n do begin for j:=1 to i do write(a[i,j]:3); writeln; end;} writeln(f[1,1]);end.

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息