更难的矩阵取数问题(dp)

2024-02-19 09:38
文章标签 问题 dp 矩阵 取数 更难

本文主要是介绍更难的矩阵取数问题(dp),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

更难的矩阵取数问题

分析: 只走一次的问题我们之前分析过。现在要走两次,有什么好办法呢? 我们设想,有两个人都从左上角走到右下角,这和走到终点再返回是一样的,我们可以dp么?怎么dp?先看看按照之前那种方法dp两次行不行? 看下图:

如果第一条路径先找最优的,就要走路径(1,1)->(1,2)->(1,3)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)。

但是这样(1,5)和(5,3)的两个100就分开了,第二条路径至多取到一个100。事实上,我们可以选取这样的两条路径:

(1,1)->(1,2)->(1,3)->(1,4)->(1,5)->(2,5)->(3,5)->(4,5)->(5,5)
(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(5,3)->(5,4)->(5,5)

这两条路径取得了全部的100,这两条路径是最优的!



没招了么?其实我们可以“两个人一起”dp(让两个人同时走)。

用dp[x1][y1][x2][y2]表示第一个人在(x1,y1) 并且第二个人在(x2,y2)时的最大值。

我们有初值dp[1][1][1][1] = a[1][1], 求的是dp[m][n][m][n]。

问题来了: 每个人走一步,状态转移是什么?

dp[x1][y1][x2][y2] = max{dp[x1’][y1’][x2’][y2’]} + a[x1][y1] + a[x2][y2]
其中(x1’,y1’)是(x1,y1)的邻居,(x2’,y2’)是(x2,y2)的邻居。

事实上,因为我们有这个等式提示我们其实只要用3维就可以表示这个矩阵,因为 y2 = x1 + y1 – x2所以那一维可以用走多少步表示出来。

dp[step + 1][x1][x2] = max{dp[step][x1’][x2’]} + a[x1][y1] + a[x2][y2]

图中为step做了编号。

然而这个dp并没有体现出走到相同格子,数字仅计算一次的要求。那么我们加上这个条件:如果x1 = x2,dp[step + 1][x1][x2] = max{dp[step][x1’][x2’]} + a[x1][y1]。


最后,我们来提供输入输出数据,由你来写一段程序,实现这个算法,只有写出了正确的程序,才能继续后面的课程。


输入

第1行:2个数M N,中间用空格分隔,为矩阵的大小。(2 <= M, N <= 200)
第2 - N + 1行:每行M个数,中间用空格隔开,对应格子中奖励的价值。(1 <= A[i,j] <= 10000)

输出

输出能够获得的最大价值。

输入示例

3 3
1 3 3
2 1 3
2 2 1

输出示例

17


代码:

#include<iostream>
#include<cstring>
using namespace std;int dp[405][205][205];  //放在main()里会崩,因为数组太大
int a[205][205];  //放里面一个超大的数据过不了int main()
{int m,n;cin>>m>>n;for(int i=0;i<n;i++){for(int j=0;j<m;j++)cin>>a[i][j];}memset(dp,0,sizeof(dp));dp[0][0][0]=a[0][0];int x1,y1,x2,y2;for(int i=1;i<n+m;i++){for(x1=0;x1<n&&i-x1>=0;x1++){for(x2=0;x2<n&&i-x2>=0;x2++){if(x1>=1&&x2>=1)  //不在起点dp[i][x1][x2]=max(dp[i][x1][x2],dp[i-1][x1-1][x2-1]+a[x1][i-x1]+(x1==x2?0:a[x2][i-x2]));if(x1<=i-1&&x2>=1)  //x1不动,x2动。  即x1代表向右走,x2向下走dp[i][x1][x2]=max(dp[i][x1][x2],dp[i-1][x1][x2-1]+a[x1][i-x1]+(x1==x2?0:a[x2][i-x2]));if(x1>=1&&x2<=i-1)  //x1动,x2不动。dp[i][x1][x2]=max(dp[i][x1][x2],dp[i-1][x1-1][x2]+a[x1][i-x1]+(x1==x2?0:a[x2][i-x2]));if(x1<=i-1&&x2<=i-1)  //x1、x2都不动dp[i][x1][x2]=max(dp[i][x1][x2],dp[i-1][x1][x2]+a[x1][i-x1]+(x1==x2?0:a[x2][i-x2]));}}}cout<<dp[n+m-1][n-1][n-1]<<endl;return 0;
}

这篇关于更难的矩阵取数问题(dp)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/724278

相关文章

解决Maven项目idea找不到本地仓库jar包问题以及使用mvn install:install-file

《解决Maven项目idea找不到本地仓库jar包问题以及使用mvninstall:install-file》:本文主要介绍解决Maven项目idea找不到本地仓库jar包问题以及使用mvnin... 目录Maven项目idea找不到本地仓库jar包以及使用mvn install:install-file基

usb接口驱动异常问题常用解决方案

《usb接口驱动异常问题常用解决方案》当遇到USB接口驱动异常时,可以通过多种方法来解决,其中主要就包括重装USB控制器、禁用USB选择性暂停设置、更新或安装新的主板驱动等... usb接口驱动异常怎么办,USB接口驱动异常是常见问题,通常由驱动损坏、系统更新冲突、硬件故障或电源管理设置导致。以下是常用解决

Mysql如何解决死锁问题

《Mysql如何解决死锁问题》:本文主要介绍Mysql如何解决死锁问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录【一】mysql中锁分类和加锁情况【1】按锁的粒度分类全局锁表级锁行级锁【2】按锁的模式分类【二】加锁方式的影响因素【三】Mysql的死锁情况【1

SpringBoot内嵌Tomcat临时目录问题及解决

《SpringBoot内嵌Tomcat临时目录问题及解决》:本文主要介绍SpringBoot内嵌Tomcat临时目录问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录SprinjavascriptgBoot内嵌Tomcat临时目录问题1.背景2.方案3.代码中配置t

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

如何解决idea的Module:‘:app‘platform‘android-32‘not found.问题

《如何解决idea的Module:‘:app‘platform‘android-32‘notfound.问题》:本文主要介绍如何解决idea的Module:‘:app‘platform‘andr... 目录idea的Module:‘:app‘pwww.chinasem.cnlatform‘android-32

kali linux 无法登录root的问题及解决方法

《kalilinux无法登录root的问题及解决方法》:本文主要介绍kalilinux无法登录root的问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,... 目录kali linux 无法登录root1、问题描述1.1、本地登录root1.2、ssh远程登录root2、

SpringBoot应用中出现的Full GC问题的场景与解决

《SpringBoot应用中出现的FullGC问题的场景与解决》这篇文章主要为大家详细介绍了SpringBoot应用中出现的FullGC问题的场景与解决方法,文中的示例代码讲解详细,感兴趣的小伙伴可... 目录Full GC的原理与触发条件原理触发条件对Spring Boot应用的影响示例代码优化建议结论F

MySQL 中查询 VARCHAR 类型 JSON 数据的问题记录

《MySQL中查询VARCHAR类型JSON数据的问题记录》在数据库设计中,有时我们会将JSON数据存储在VARCHAR或TEXT类型字段中,本文将详细介绍如何在MySQL中有效查询存储为V... 目录一、问题背景二、mysql jsON 函数2.1 常用 JSON 函数三、查询示例3.1 基本查询3.2

Pyserial设置缓冲区大小失败的问题解决

《Pyserial设置缓冲区大小失败的问题解决》本文主要介绍了Pyserial设置缓冲区大小失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录问题描述原因分析解决方案问题描述使用set_buffer_size()设置缓冲区大小后,buf