首页 > 其他 > 详细

摘花生

时间:2020-05-22 20:30:45      阅读:43      评论:0      收藏:0      [点我收藏+]

技术分享图片

 

 技术分享图片

 

 首先,这是一道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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!