晴天小猪历险记之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.

版权声明：本站所有文章皆为原创，欢迎转载或转发，请保留网站地址和作者信息。

很赞哦！ ()