算法训练 方格取数 时间限制：1.0s 内存限制：256.0MB 问题描述 设有N*N的方格图(N<=10),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。 某人从图的左上角的A 点(1,1)出发，可以向下行走，也可以向右走，直到到达右下角的B点(N,N)。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。 此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。 输入格式 输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。 输出格式 只需输出一个整数，表示2条路径上取得的最大的和。 样例输入 8 2 3 13 2 6 6 3 5 7 4 4 14 5 2 21 5 6 4 6 3 15 7 2 14 0 0 0 样例输出 67
思路分析：刚开始的想法是走两次，第一次边走边记录路径，然后倒推把走过的点权值标记成0。然后再从左上角开始第二次走。所以使用两次dp，求和。
但是这么做是错的。因为这么做是每次求出最大值，本质是贪心的思想，不是动态规划。分两次的话得到的是局部最优解，但这是整体最优解吗？可以找出一个反例：
7 1 3 2 1 4 3 2 3 3 3 3 3 5 5 4 6 5 4 7 3 2 7 5 4 0 0 0
假如输入样例如上，如果用两次dp的方法，第一次是20，第二次是3，所以最后的权值是23。但是你再看看，我们可以把这个方格的数都取完的，第一次取的权值是17，第二次取得8，这样就是25了。显然这是一个反例，我们上述的想法是错误的。
后来上网查了一下，原来是2000年的NOIP提高组（好变态），很巧妙的想法是模拟成两个人同时走。。原来这是个经典的问题，多线程DP。。。
转移方程如下：
dp[x1][y1][x2][y2] = max( dp[x1 - 1][y1][x2 - 1][y2], dp[x1 - 1][y1][x2][y2 - 1], dp[x1][y1 - 1][x2][y2 - 1], dp[x1][y1 - 1][x2 - 1][y2] )
dp[x1][y1][x2][y2]代表的含义是第一个人和第二个人同时走，第一个人走到（x1, y1），第二个人走到（x2, y2）时候的最大值。
dp[x1 - 1][y1][x2 - 1][y2]：这两个人都是从左边走过来的
dp[x1][y1 - 1][x2][y2 - 1]：这两个人都是从上边走过来的
dp[x1 - 1][y1][x2][y2 - 1]：第一人从左边走过来，第二个人从上边走过来
dp[x1][y1 - 1][x2 - 1][y2]：第一人从上边走过来，第二个人从左边走过来
然后需要注意的是，如果x1 == x2 && y1 == y2，此时两个人是走到同一个点了，但是这个点的权值只能加一次，因为要模拟走过一次，这个点就要变成0的情况。
/* dp[x1][y1][x2][y2] = max( dp[x1 - 1][y1][x2 - 1][y2], dp[x1 - 1][y1][x2][y2 - 1], dp[x1][y1 - 1][x2][y2 - 1], dp[x1][y1 - 1][x2 - 1][y2] ) */ #include <cstdio> #include <algorithm> #define MAX 10 + 10 using namespace std; int MGraph[MAX][MAX]; int dp[MAX][MAX][MAX][MAX]; int main() { //freopen( "123.txt", "r", stdin ); int n; int x, y, num; scanf( "%d", &n ); while( 1 ) { scanf( "%d%d%d", &x, &y, &num ); if( x == 0 && y == 0 && num == 0 ) break; MGraph[x][y] = num; } dp[1][1][1][1] = MGraph[1][1]; for( int x1 = 1; x1 <= n; x1++ ) { for( int y1 = 1; y1 <= n; y1++ ) { for( int x2 = 1; x2 <= n; x2++ ) { for( int y2 = 1; y2 <= n; y2++ ) { if( x1 + y1 != x2 + y2 ) continue; int temp; temp = max( dp[x1 - 1][y1][x2 - 1][y2], dp[x1 - 1][y1][x2][y2 - 1] ); temp = max( temp, dp[x1][y1 - 1][x2][y2 - 1] ); temp = max( temp, dp[x1][y1 - 1][x2 - 1][y2] ); if( x1 == x2 && y1 == y2 ) { dp[x1][y1][x2][y2] = temp + MGraph[x1][y1]; } else { dp[x1][y1][x2][y2] = temp + ( MGraph[x1][y1] + MGraph[x2][y2] ); } } } } } printf( "%d\n", dp[n][n][n][n] ); return 0; }
