UC知道pascal 方格取数
来源：百度知道 编辑：UC知道 时间：2024/05/11 18:59:51
背景 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 l
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;