P1004 方格取数

https://www.luogu.org/problem/show?pid=1004#sub

四维做法基于可以看做俩个人，同时走。
从左上角到右下角步数是一定的，所以可以压缩到三维。

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int f[20][20][20],a0[20][20];
int ans,n;
int main()
{
    scanf("%d",&n);
    while(1){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(a==0&&b==0&&c==0)break;
        a0[a][b]=c;
    }
    //f[1][1][1]=a0[1][1];
    for(int k=1;k<=2*n-1;k++)//k为步数,从（1,1）—> （n,n） 需要走2*n-1步
     for(int i=1;i<=min(k,n);i++)
      for(int j=1;j<=min(k,n);j++){//j,i 为行 
        f[k][i][j]=max(max(f[k][i][j],f[k-1][i][j]),max(max(f[k-1][i][j-1],f[k-1][i-1][j]),f[k-1][i-1][j-1]));

        if(i==j)f[k][i][j]+=a0[i][k-i+1];
        else f[k][i][j]+=a0[i][k-i+1]+a0[j][k-j+1];
    } 
    printf("%d",f[2*n-1][n][n]);
    return 0;

}