题解 P1004 【方格取数】

显然，普及+提高是不会让你用两次二维dp过的~ 所以需要使用【多进程dp】 思路就是同时进行两条路径， 保证在更新每一个点时，两个点的步数相同； 下面是实现 定义d【i】【j】【k】为走了j步，路径a向下了j，路径b向下了j时，取数和的最大值； 此时（i-j），（i-k）就是a与b此时到达点的横坐标； 那么，会有4种可能， 从a的上，b的上到达a与b； 从a的左，b的上到达a与b； 从a的上，b的左到达a与b； 从a的左，b的左到达a与b； 然后对这4种取一个max就好了 之后，如果a与b重合了 每个点只能取一次，那么我们减一个点就好了； ```cpp #include<stdio.h> //没有algorithm，因为max是4参数的; using namespace std; int n;int map[9][9]; int d[18][9][9];int res; //dp的三维数组； int max(int a,int b,int c,int d) { return (((((a>b)?a:b)>c)?((a>b)?a:b):c)>d)?((((a>b)?a:b)>c)?((a>b)?a:b):c):d; //丧心病狂的条件表达式，代码是不是很简洁~ } int main() { scanf("%d",&n); while (1) { int x;int y;int val; scanf("%d%d%d",&x,&y,&val); if(x==0&&y==0&&val==0)break; map[x-1][y-1]=val; } //读入，死循环，收到结束信号就break d[0][0][0]=map[0][0];//边界，初始化 for(int i=0;i<2*n;i++)//三重循环。 { for(int j=0;j<=i&&j<n;j++) { for(int k=0;k<=i&&k<n;k++) { if(i==0&&j==0&&k==0)continue; d[i][j][k]=map[j][i-j]+map[k][i-k]+ max(d[i-1][j][k],d[i-1][j-1][k-1],d[i-1][j-1][k],d[i-1][j][k-1]);//max4个 if(j==k)d[i][j][k]-=map[j][i-j]; //去重 } } } res=d[2*(n-1)][n-1][n-1];//从零开始的数组，记得-1~ printf("%d",res); return 0;//拜拜程序~ } ```