[普及+/提高]P1004 矩阵取数

题目链接：https://www.luogu.com.cn/problem/P1004

思路分析

从题目中我们也许会想到有关路径的东西，比如前面说过的回溯和广搜，但同时也会发现一个问题，就是这个取的最大值是走两次后所取得的结果，而回溯和广搜往往针对一次过程。

也许你也会想，那就来两次回溯和广搜呗！我们也希望能够这样做，可问题是，执行了第一次后，怎么确定第二次所走的矩阵数据？我们怎么确定第一次取得结果所取走的是哪些数呢？这是个需要思考的问题。而且事实上，你大致的估计一下回溯和广搜的时间复杂度，因为这个矩阵从起点走到终点的路径相当的多，以广搜为例，时间复杂度可能是O(2^n)(好像吧，因为这个每个点都有两条路可以走，然后在某一次中重复走过的点不用标记，照样可以重复走，路线可以有重复的部分)

那么我们可以尝试考虑两人同时行动。

数组是个好东西，它不仅可以存放数据，表示数据，事实上还可以用来建立抽象模型，这也是数组的更高层次的应用，需要一定经验的积累。我们尝试着这样建模：

a[i][j][n][k] = max(a[i-1][j][n-1][k],a[i-1][j][n][k-1],a[i][j-1][n-1][k],a[i][j-1][n][k-1]) + map[i][j] + map[n][k]

a[i][j][n][k]表示两人从起点出发分别到达(i,j),(n,k)位置时两人一共所取到的数的和，那么我们考虑到这个值就是前一步可能位置的最大值 + 走后取到的数，而前一步走到该位置有如下可能：

第一个人向下走，第二个人向下走到达该位置，即原位置是(i-1,j),(n-1,k)
第一个人向下走，第二个人向右走到达该位置，即原位置是(i-1,j),(n,k-1)
第一个人向右走，第二个人向下走 ......
第一个人向右走，第二个人向右走 ......

其中，当两个人走到同一个位置的时候，显然重复取数了，就要额外减去一个这样的重复数，即 (i,j) == (n,k) 时，去重。你可能会想，这个去重式子只表示了走到该点时去重，那么两人的路径上的交点呢？不用担心，这个过程是一个连续进行的过程，每一点都和前面的点有关系，你可以想一下，a1 的值中没有重复的成分(执行了去重工作)，那么 a2 = a1 +map 的结果中同样也不会有重复的成分(当然在这一点也执行了去重工作)，所以一直下去，每一个点的结果都是去重过的值，也就是说没有重复的成分在里面

显然，要遍历所有的点，因为是四维数组，所以需要四层循环，好在这个问题的矩阵宽度 N ≤ 9，也不会超时。

但事实上，还可以进行优化一下，这个公式中的下标表示的就是两人走到的位置的坐标，我们可以改变一坐标的表示方法。

我们设 L 为所走的步数(一步为一个单位)，起点坐标为 (0,0)，X 为走到位置的横坐标，那么我们就可以得到纵坐标为 L-X 这样的话，我们同样可以表示坐标，而且两人的坐标表示可以共同使用 L 这个参数，这样的话四维就降到了三维。

即 a[L][i][j] , 两人的坐标分别为 (i,L-i),(j,L-j)，两人同样可以遍历所有的点，当然也要进行去重工作

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int maap[13][13],f[21][13][13];      //第二个 第三个 表示该位置的行
int main(){
    int N,r,c,data;
    cin>>N>>r>>c>>data;
    while(r&&c&&data){                //输入数据
        maap[r][c]=data;
        cin>>r>>c>>data;
    }
    f[0][1][1]=maap[1][1];          //因为循环中没有判断没有走的情况，所以自行初始化一下
    for(int l=1;l<=2*(N-1);l++)
        for(int i=1;i<=l+1&&i<=N;i++)
            for(int j=1;j<=l+1&&j<=N;j++){
                f[l][i][j]=max(f[l-1][i][j],max(f[l-1][i-1][j],max(f[l-1][i][j-1],f[l-1][i-1][j-1])))+maap[i][2+l-i]+maap[j][2+l-j];          //公式来了
                if(i==j) f[l][i][j]-=maap[i][2+l-i];         //去重
            }
    cout<<f[2*(N-1)][N][2+2*(N-1)-N];
    return 0;
}

事实上，这个算法有个名字，叫 "动态规划"，这个东西没有什么具体可言的操作性，因为它的概念其实就有点抽象，大家可以百度一下了解了解。

另外，有大佬把数组的维度降到了二维，二维的思路有点新奇，别问我具体怎么实现，我也不懂！！！所以就放弃了！！！

[普及+/提高]P1004 矩阵取数

思路分析

代码

评论(0)