pascal 方格取数

三取方格数
背景 Background
JerryZhou同学经常改编习题给自己做。
这天，他又改编了一题。。。。。
描述 Description
设有N*N的方格图，我们将其中的某些方格填入正整数，
而其他的方格中放入0。
某人从图得左上角出发，可以向下走，也可以向右走，直到到达右下角。
在走过的路上，他取走了方格中的数。（取走后方格中数字变为0）
此人从左上角到右下角共走3次，试找出3条路径，使得取得的数总和最大。
输入格式 Input Format
第一行:N (4<=N<=20)
接下来一个N*N的矩阵，矩阵中每个元素不超过80，不小于0
输出格式 Output Format
一行，表示最大的总和。
样例输入 Sample Input
4
1 2 3 4
2 1 3 4
1 2 3 4
1 3 2 4
样例输出 Sample Output
39
注释 Hint
多进程DP

题解：想想对于当前已经走了K步，三个棋子的横坐标也已经知道，那么它们的纵坐标......那这三点是怎么走到的？也就是他们的前一步可能是什么。一但确定了走了几步和横坐标，就可以确定下来纵坐标。同样，一旦确定了走了几步和纵坐标，就可以确定下来横坐标。
用f[k,x,y,z]表示当走到第k步时,且三人横坐标分别为x,y,z时..所取数的最大值..由于每一个人都可以由2个方向推来..所以一共有2^3=8种状态
wa因：红色部分，最外层循环必然是k步，内层循环的终值是当前走到了第几步而不是n，因为，走k步时，横坐标最多到k

program :
program p1143;
var f:array[0..40,0..20,0..20,0..20]of longint;
f1,f2:text;
n,k,k1:longint;
a:array[1..20,1..20]of longint;
procedure init;
var i,j:longint;
begin

read(n);k:=2*n-1;
for i:=1 to n do
for j:=1 to n do
read(a[i,j]);
fillchar(f,sizeof(f),0);
end;
function s(i,a1,a2,a3:longint):longint;
{这个整个的function 我只知道它的用处，不知道为什么这样写}
var b1,b2,b3,k1:longint;
begin
k1:=i 1;
b1:=k1-a1;b2:=k1-a2;b3:=k1-a3;
{ writeln(b1,b2,b3);}
if (a1=a2)and(a1=a3) then exit(a[a1,b1]);
if (a1=a2)or(a2=a3)or(a1=a3) then
begin
if (a1=a2) then exit(a[a1,b1] a[a3,b3]);
if(a1=a3) then exit(a[a1,b1] a[a2,b2]);
if (a2=a3) then exit(a[a1,b1] a[a2,b2]);
{exit(a[a1,b1] a[a2,b2]); 中的那个空格是什么意思？}
end;
exit(a[a1,b1] a[a2,b2] a[a3,b3]);
{上面的都不知道怎么来的}
end;
procedure dp;
var i,a1,a2,a3,t,min:longint;
begin
f[1,1,1,1]:=a[1,1];
for i:=2 to k do
for a1:=1 to i do
for a2:=1 to i do
for a3:=1 to i do
begin
t:=s(i,a1,a2,a3);min:=-1;
{ writeln(t);}
if f[i-1,a1,a2,a3]>min then min:=f[i-1,a1,a2,a3];
if f[i-1,a1-1,a2-1,a3-1]>min then min:=f[i-1,a1-1,a2-1,a3-1];
if f[i-1,a1-1,a2,a3]>min then min:=f[i-1,a1-1,a2,a3];
if f[i-1,a1,a2-1,a3]>min then min:=f[i-1,a1,a2-1,a3];
if f[i-1,a1,a2,a3-1]>min then min:=f[i-1,a1,a2,a3-1];
if f[i-1,a1-1,a2-1,a3]>min then min:=f[i-1,a1-1,a2-1,a3];
if f[i-1,a1-1,a2,a3-1]>min then min:=f[i-1,a1-1,a2,a3-1];
if f[i-1,a1,a2-1,a3-1]>min then min:=f[i-1,a1,a2-1,a3-1];
f[i,a1,a2,a3]:=min t;
{min t 这个事什么意思？以前没用过}
end;
writeln(f[k,n,n,n]);
end;
begin
init;
dp;

end.

高手顺便把 http://wenwen.sogou.com/z/q746161772.htm 也解决了吧！ 谢谢了

var i,j,k,m,n,p,l:longint;
x,y,xx,yy,xxx,yyy,x1,x2,x3,y1,y2,y3:longint;
f,f1:array[1..20,1..20,1..20] of longint;
b:array[1..50,1..50] of boolean;
a:array[1..20,1..20] of longint;
d1,d2,d3:longint;

begin
readln(n);
fillchar(b,sizeof(b),0);
for i:=1 to n do
for j:=1 to n do
begin
read(a[i,j]);
b[i,j]:=true
end;
k:=n+n-1;
f[1,1,1]:=a[1,1];
for i:=2 to k do
begin
fillchar(f1,sizeof(f1),0);
for x:=1 to i-1 do
for xx:=1 to i-1 do
for xxx:=1 to i-1 do
begin
y:=i-x;
yy:=i-xx;
yyy:=i-xxx;
if b[x,y] and b[xx,yy] and b[xxx,yyy] then
for d1:=0 to 1 do
for d2:=0 to 1 do
for d3:=0 to 1 do
begin
if d1=0 then begin x1:=x+1;y1:=y end
else begin x1:=x;y1:=y+1 end;
if d2=0 then begin x2:=xx+1;y2:=yy end
else begin x2:=xx;y2:=yy+1 end;
if d3=0 then begin x3:=xxx+1;y3:=yyy end
else begin x3:=xxx;y3:=yyy+1 end;
if b[x1,y1] and b[x2,y2] and b[x3,y3] then
begin
if (x1=x2)and(x2=x3) then
if f1[x1,x2,x3] f1[x1,x2,x3]:=f[x,xx,xxx]+a[x1,y1];
if (x1=x2)and(x2<>x3) then
if f1[x1,x2,x3] then f1[x1,x2,x3]:=f[x,xx,xxx]+a[x1,y1]+a[x3,y3];
if (x1<>x2)and(x2=x3) then
if f1[x1,x2,x3] then f1[x1,x2,x3]:=f[x,xx,xxx]+a[x1,y1]+a[x3,y3];
if (x1=x3)and(x2<>x3) then
if f1[x1,x2,x3] then f1[x1,x2,x3]:=f[x,xx,xxx]+a[x1,y1]+a[x2,y2];
if (x1<>x3)and(x1<>x2)and(x2<>x3) then
if f1[x1,x2,x3] then f1[x1,x2,x3]:=f[x,xx,xxx]+a[x1,y1]+a[x3,y3]+a[x2,y2]
end
end
end;
f:=f1
end;
writeln(f[n,n,n])
end.

用了滚动数组，以斜线为阶段，多进程动态规划

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

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