#P1004 方格取数
题目描述
设有N*N*的方格图(N<=9)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字0。如下图所示（见样例）：
A 0 0 0 0 0 0 0 0
0 0 13 0 0 6 0 0
0 0 0 0 7 0 0 0
0 0 0 14 0 0 0 0
0 21 0 0 0 4 0 0
0 0 15 0 0 0 0 0
0 14 0 0 0 0 0 0
0 0 0 0 0 0 0 0
. B
某人从图的左上角的A点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从A点到B点共走两次，试找出2条这样的路径，使得取得的数之和为最大。
##输入输出格式
###输入格式：
输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。
###输出格式：
只需输出一个整数，表示2条路径上取得的最大的和。
##输入输出样例
###输入样例#1：
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
###输出样例#1：
67
##说明
NOIP 2000 提高组第四题
#分析
根据数据范围，显然不能采用搜索。
如果直接按照题目编写dp，显然具有后效性。在dp中无法记录走过的路径，更不可能把“走过的路径上的数变为0”，所以对于这样的问题，一般是采用多维dp，同时将路径选出。
为了方便，可以想象成有两个人，同时从起点出发，走到终点。
用dp[i][j][k][l]表示两人分别走到了(i,j)和(k,l)这两个点。
先不考虑走过的数变为0的情况，则dp[i][j][k][l]受到这四个状态的控制：
dp[i-1][j][k-1][l]
dp[i-1][j][k][l-1]
dp[i][j-1][k-1][l]
dp[i][j-1][k][l-1]
因为要取最大的数，可以得到状态转移方程如下
dp[i][j][k][l] = max{dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]} + a[i][j] + a[k][l];
下面可以考虑走过的数变为0这个要求了。
题目告诉我们，对于每次决策，必须且只有“向下走1格”和“向右走1格”这两种可能。
所以，无论在什么时候，两个人走到的点距离起点的曼哈顿距离都是一样的，即i+j=k+l
并且，对于一个点(i,j)，从原点出发，无论怎么走，到这个点所经过的距离均为i+j
所以可以得知，当两个人选的路程有公共点时，两个人一定同时到达这个公共点。
所以只需在进行dp的时候，判断i,j是否等于k,l,如果等于，则在转移的时候只需加一遍这个格上的数即可。
#####即
dp[i][j][k][l] = max{dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]} + a[i][j];
则程序不难写出
#include <iostream>
using namespace std;
int map[15][15];
int dp[15][15][15][15];
int m;
int main()
{
cin >> m;
int x,y,n;
do{
cin >> x >> y >> n;
map[x][y] = n;
}while(x != 0 || y != 0 || n != 0);
for(int i = 1;i <= m;i++)
{
for(int j = 1;j <= m;j++)
{
for(int k = 1;k <= m;k++)
{
for(int l = 1;l <= m;l++)
{
int ma1 = max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]);
int ma2 = max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]);
dp[i][j][k][l] = max(ma1,ma2)+map[i][j]+map[k][l];
if(i == k && j == l)
{
dp[i][j][k][l] -= map[i][j];
}
}
}
}
}
cout << dp[m][m][m][m];
}复杂度达到O(n^4) 尽管对于这个题目而言，这么高的复杂度也能AC，但是仍有简单有效的优化方法。
首先考虑复杂度这么高的原因
#####状态参数太多
对于所有状态，我们需要四个参数才能区分他们，这是很不必要的。
前面提到过i+j=k+l这个关系。
变形一下，可得到l=i+j-k。
###！！！
也就是说，l这个参数可以通过前面三个参数推出来
那我还存他干什么
用dp[i][j][k]表示两人分别走到了(i,j)和(k,i+j-k)这两个点。
则状态转移方程为
dp[i][j][k] = max{dp[i-1][j][k-1],dp[i-1][j][k],dp[i][j-1][k-1],dp[i][j-1][k]} + a[i][j] + a[k][i+j-k];(i,j != k,l)
dp[i][j][k] = max{dp[i-1][j][k-1],dp[i-1][j][k],dp[i][j-1][k-1],dp[i][j-1][k]} + a[i][j];(i,j == k,l)
优化后的程序如下
#include <iostream>
using namespace std;
int map[15][15];
int dp[15][15][15];
int m;
int main()
{
cin >> m;
int x,y,n;
do{
cin >> x >> y >> n;
map[x][y] = n;
}while(x != 0 || y != 0 || n != 0);
for(int i = 1;i <= m;i++)
{
for(int j = 1;j <= m;j++)
{
for(int k = 1;k <= m;k++)
{
int l = i + j - k;
int ma1 = max(dp[i-1][j][k-1],dp[i-1][j][k]);
int ma2 = max(dp[i][j-1][k-1],dp[i][j-1][k]);
dp[i][j][k] = max(ma1,ma2)+map[i][j]+map[k][l];
if(i == k && j == l)
{
dp[i][j][k] -= map[i][j];
}
}
}
}
cout << dp[m][m][m];
}
复杂度O(n^3)