题解 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重合了

每个点只能取一次，那么我们减一个点就好了；

#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;//拜拜程序~
}