题目描述
设有N \times NN×N的方格图(N \le 9)(N≤9)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字00。如下图所示（见样例）:
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某人从图的左上角的AA点出发，可以向下行走，也可以向右走，直到到达右下角的BB点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字00）。
此人从AA点到BB点共走两次，试找出22条这样的路径，使得取得的数之和为最大。
输入输出格式
输入格式：
输入的第一行为一个整数NN（表示N \times NN×N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的00表示输入结束。
输出格式：
只需输出一个整数，表示22条路径上取得的最大的和。
输入输出样例
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 ----------------------------------------------------------------------------- 第一眼看这道题
觉得很简单呢
数据范围小
思维含量低
于是直接就写
结果
完全不对 好吧
de了半天bug
也确实找不到什么
于是迷茫了
就
打开了题解
开始找不同了 我开的滚动数组是二维的，走两边循环
而题解就nb
有4种
最最最基础的就是
开了一个4维数组 ----------------------------------------------------------------
一级
我们做题的思路可以这样：
①先看一下出题日期（毕竟是NOIP的题目，有一定的水准），然后发现是2000年的普及第四题
我们要知道的是，好像比较前面的几年由于1999的数塔IOI问题后，接下来几年的最后一两题都很喜欢出DP
所以，我们首先看一下题目的内容，求路径最大的方法，这时候就要想到DP或者DFS
②然后我们发现题目的数据规模不大，n<=9，所以我们可以考虑用DFS或者DP都可以
但是鉴于 "好像比较前面的几年由于1999的数塔IOI问题后，接下来几年的最后一两题都很喜欢出DP "
我们觉得用DP会比较好
③而且，NOIP的压轴DP题你想要2维过（在考场上是很难想出来的）
所以我们考虑高维
④我们找到一个东西叫做四维DP，因为这题是两个人走，我们思考一下能不能单纯用两个人的模拟过呢？
显然是可以的，我们记f[i][j][k][l]表示第1条路线的i,j走法和第2条路线的k,l走法
显然我们可以两个人一起走，复杂度最多就是9*9*9*9=6561（哈哈哈时间复杂度这么低）
所以我们就用这个方法了！
⑤然后我们思考动归方程的写法：
第1条路线只可能是从i-1,j或者i,j-1转移，第2条路线也只可能从k-1,l或者k,l-1转移
而且因为是2个人走，如果走到一点我们的那个点就要打标记说那点上面的值为0
所以我们得到了我们的动归方程（注意：万一i,j与k,l相同这是要小心的！）
f[i][j][k][l]=max(f[i-1][j][k-1][l],f[i][j-1][k-1][l],f[i-1][j][k][l-1],f[i][j-1][k][l-1])+a[i][j]+a[k][l];
⑥最后这题就完美解决啦
二级
然而这题数据太弱，范围这么小偶也没想到，但是钻研的精神很可贵，还是要多想想。
像楼下说的，用三维数组，优化空间。可以用路径长度代表阶段
f(l,i,ii)表示当前路径长度为l（也就是说当前是第l个状态），第一个人走到(i,l-i)的位置，第二个人走到(ii,l-ii)的位置。
具体原因楼下同样讲得太多了，因为后面还有料，现在就不多说了。
三级
看过楼下题解的同学应该能够发现，每一次的状态转移都只和上一个阶段有关，即第l-1个阶段。
所以说可以用滚动数组，只记录当前阶段和2的余数的阶段即可。
若l%2==0，则上一个状态l%2==1。反之亦然。
这样空间复杂度从O(n^4)->O(n^3)->O(2n^2)
四级
四级
其实这样已经差不多了，但是还可以继续优化。
如果对01背包的以为写法非常熟悉的话......
可以模仿，枚举i和ii的时候，如果倒着做，那么当前的值就是上一个阶段的值，连滚动数组都不用。
空间复杂度再降到O(n^2)
个人的简单的四维代码如下：
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
int n,a[][],f[][][][],x,y,z;
memset(a,,sizeof(a));
memset(f,,sizeof(f));
scanf("%d",&n);
while()
{
scanf("%d%d%d",&x,&y,&z);
if(x == &&y == &&z == )
break;
a[x][y]=z;
}
f[][][][]=a[][];
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
for(int o=;o<=n;o++)
for(int u=;u<=n;u++)
{
f[i][j][o][u]=max( max(f[i-][j][o-][u],f[i][j-][o-][u]),max(f[i-][j][o][u-],f[i][j-][o][u-]))+a[i][j]+a[o][u];
if(i == o &&j == u)
f[i][j][o][u]-=a[i][j];
}
printf("%d",f[n][n][n][n]);
return ;
}
如下二维代码
#include<cstdio>
#include<algorithm>
using namespace std;
struct point
{
int x,y,data;//记录每个点的位置和数值
}p[];
int n,m,map[][],f[][];
int main()
{
int i,ii,j,jj,l;
scanf("%d",&n);
while()
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(!a&&!b&&!c)
break;
p[++m].x=a;
p[m].y=b;
p[m].data=c;
}
for(i=;i<=m;i++)
map[p[i].x][p[i].y]=p[i].data;
for(l=;l<=n*;l++)//每个点最少横着竖着都走一格，最多都走n格就到终点
for(i=l-;i>=;i--)//和前面说的一样，倒着做
for(ii=l-;ii>=;ii--)
{
j=l-i;jj=l-ii;//i+j=ii+jj=l
f[i][ii]=max(max(f[i][ii],f[i-][ii-]),max(f[i-][ii],f[i][ii-]))+map[i][j];
//重点说明一下吧，这里省略了很多。如果i不减1，意思就是j-1，因为上一个阶段就是l-1嘛。如果ii-1，意思就是说jj不减1。
f[i][ii]+=map[ii][jj]*(i!=ii);
//如果i==ii，其实就是(i==ii&&j==jj)，因为和都是l嘛。如果走过一遍，第二遍走得到的值就是0（题目上说的）。
}
printf("%d\n",f[n][n]);
//输出意思是在路径长度为2*n的阶段，两遍都走到(n,n)的最优值。因为在这里(j=2*n-i=n,jj=2*n-ii=n),所以走到的就是(n,n)的位置
return ;
}
找了大佬帮忙
于是明白了
我一开始循环两遍的dp
两遍dp之间不是最优的
也就是说
虽然
第一个dp是最优的
下一个dp是在剩余情况下的（无奈下的）最优
所以
得到的答案
不是最优