首先,这是一道DP的题嗯嗯 ……
既然这道题一个测试点有多张地图,所以我就定义了一个三维数组map来存储每一张矩阵图。
与此同时,再开一个数组dp[105][105][105]来表示每张图上从左上角的起始点到每个点能摘到的最多的花生。
再然后,开一个c[105]数组,一个r[105]数组来存储每张图的边界。
最后再开一个指针i表示当前在研究第几个矩阵、指针j表示该个正在被研究的数组的行,指针h表示该个正在被研究的数组的列。
这样,main函数以前的定义部分就写好了。
main函数内,先输入矩阵的数量,然后开始第一个for循环枚举研究第一个矩阵。
在大循环内,首先我们要读入每一张矩阵的长和宽c[i]和r[i],然后读入这张地图。
接下来,要对dp数组进行初始化。
先初始化dp[i][1][1]为map[1][1][1],因为这个位置没有其它位置可以到达。
然后初始化第一行和第一列,其中第一行只能从左边过来,第一列只能从上边到来,所以
这样我们就得到了进一步完善的代码:
最后就是最重要的DP部分!
首先,第一行和第一列已经初始化完成,所以要从第二行、第二列开始枚举。
然后,我们要考虑让该点的dp值更大(摘更多的花生)应该从左边来还是从上面来(因为题目中说只能往下走或往右走)。
至于从那边走,就交给计算机。这里可以用一个max函数,我用了STL中的头文件<algorithm>
我们算出了从那边过来该点的dp值更大,再加上在这个点能摘的花生数,就可以得出该点最多能摘几个花生。
这样就得出了状态转移方程。
这样,我们就又一次完善了我们的代码。(前面记得要加头文件,为保证代码清晰度省略)
最后还需要输出!
这很简单,只需要输出每个矩阵最右下角的位置的数值即可(因为其它位置都还能再移动去摘花生)
这样,我们就得到了完整的代码。
最后我们只需要点一下提交,就会惊喜地发现:
这就是关于本题的具体讲解。由于第一次发DP题的题解,生怕翻车。码风有可能有些奇怪。。。。。。
原文:https://www.cnblogs.com/qianr/p/12938211.html