最原始的方程就是三角形那个,但是在此基础上还需要一些改进。。
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;