8786:方格取数 （多线程dp）

【题目描述】

　　　　设有N*N的方格图(N<=10),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。 此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。

【题目链接】

　　　　http://noi.openjudge.cn/ch0206/8786/

【算法】

　　　　醉了，一开始以为很简单分成两次呗，走完一遍第一次路径经过的点记为0，但是感觉有点不对劲，因为第一次走过路可能会影响第二次，也就是有后效性，分开计算状态空间中有很多种情况并没有遍历到。然后看书。。。。所以要多线程dp，设dp【a】【b】【c】【d】表示第一次走到【a】【b】点第二次走到【c】【d】点状态下获得的最大分数，状态方程倒是不难。

【代码】

 #include <bits/stdc++.h>

 using namespace std;

 int n,i,j,tmp,a,b;

 int puz[][],dp[][][][];

 int main()

 {

     scanf("%d",&n);

     while(scanf("%d%d%d",&i,&j,&tmp)&&i)

         puz[i][j]=tmp;

     for(i=;i<=n;i++)

     for(j=;j<=n;j++)

     for(a=;a<=n;a++)

     for(b=;b<=n;b++) {

         dp[i][j][a][b]=max(max(dp[i-][j][a-][b],dp[i][j-][a][b-]),

                            max(dp[i-][j][a][b-],dp[i][j-][a-][b]))+puz[i][j];

         if(i!=a||j!=b) dp[i][j][a][b]+=puz[a][b];

     }

     printf("%d\n",dp[n][n][n][n]);

     return ;

 }