【洛谷】【动态规划】P1006:传纸条(C/C++)

这篇具有很好参考价值的文章主要介绍了【洛谷】【动态规划】P1006:传纸条(C/C++)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

传纸条

题目描述

小渊和小轩是好朋友也是同班同学,他们在一起 总有谈不完的话题。一次素质拓展活动中,班上同学安排做成一个m行n列的矩阵,而小渊和小轩被安排在矩阵对角线的两端,因此,他们就无法直接交谈了。幸运的是,他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里,小渊坐在矩阵的左上角,坐标(1,1),小轩坐在矩阵的右下角,坐标(m,n)。 从小渊传到小轩的纸条只可以向下或者向右传递,从小轩传给小渊的纸条只可以向上或者向左传递。
在活动进行中,小渊希望给小轩传递一张纸条,同时希望小轩给他回复。班里每个同学都可以帮他们传递,但只会帮他们一次,也就是说如果此人在小渊递给小轩纸条的时候帮忙,那么在小轩递给小渊的时候就不会再帮忙。反之亦然。
还有一件事情需要注意,全班每个同学愿意帮忙的好感度有高有低(注意:小渊和小轩的好心程度没有定义,输入时用0表示),可以用一个0-100的自然 数来表示,数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条,即找到来回两条传递路径,使得这两条路径上同学的好心程度只和最大。 现在,请你帮助小渊和小轩找到这样的两条路径。

输入格式

输入第一行有2个用空格隔开的整数m和n,表示班里有m行n列(1<=m,n<=50)。
接下来的m行是一个m*n的矩阵,矩阵中第i行j列的整数表示坐在第i行j列的学生的好心程度。每行的n个整数之间用空格隔开。

输出格式

输出文件共一行一个整数,表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。

输入输出样例

输入样例

3 3
0 3 9
2 8 5
5 7 0

输出样例

34

解题思路

本题作为一道动态规划的题目,麻烦就麻烦在本题要找两条最优路径,且不能重复,虽然一条从左上角到右下角,一条从右下到左上,但其实可以看成从左上角找两条不相交的好心值最大的路径到右下角。

错误避坑

本题我一开始想的是用两个二维数组来分别存两条路径,对于第一条路径,如果从左上往右下走的话,对于每一个坐标点,它顶多只能是由它上面的那个点抑或是它左边的那个点过来的,因此可以得到一个二维的动态转移方程:dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) + arr[i][j],以此得到第一条从左上到右下的路径,再倒着遍历把第一条路径经过的点标记为0,最后再用动态转移方程遍历得到第二条路径,但这样有时候第一条路径会把路给堵死,使得第二条路无法在不经过第一条路的前提下到达终点。例如,输入样例中,如果先只考虑一条路的话,就应该是先往右到3,再往下到8,再往下到7,最后往右到终点。如此,第二条路就走不通了。

0 3 x
x 8 x
x 7 0
正确思路

因此选择用四维数组dp,用dp[i][j][k][l]来表示(存储)从起点到坐标点(i,j)和(k,l)所能得到的最大好感度,要到达(i,j)和(k,l)共有四种情况,分别为(i)(j - 1)(k - 1)(l), (i)(j - 1)(k)(l - 1), (i - 1)(j)(k)(l - 1), (i - 1)(j)(k - 1)(l),到达它们能得到的最大好感度分别为dp[i][j - 1][k - 1][l], dp[i][j - 1][k][l - 1], dp[i - 1][j][k][l - 1], dp[i - 1][j][k - 1][l] ,取它们之中的最大值,再加上(i,j)和(k,l)点的好感值arr[i][j] ,arr[k][l],即可得到dp[i][j][k][l]。
由此得到动态转移方程:dp[i][j][k][l] = maxx(dp[i][j - 1][k - 1][l], dp[i][j - 1][k][l - 1], dp[i - 1][j][k][l - 1], dp[i - 1][j][k - 1][l]) + arr[i][j] + arr[k][l]
要使两条线不相交,在遍历的时候,将l的初始值设为j + 1即可,即for (int l = j + 1; l <= n; l++)
由于两条路径不能相交,所以都不能到达终点,但终点的好感值为0,因此只要一条到达终点的上面的那个点,一条到达左边的那个点,就是最终的答案,即dp[m][n - 1][m - 1][n]

AC Code

#include<cstdio>
#include<iostream>
using namespace std;
int dp[51][51][51][51] = { 0 };
int arr[51][51];
int maxx(int a, int b, int c, int d)//求得四个中的最大值
{
	int i = max(a, b);
	int j = max(c, d);
	int sum = max(i, j);
	return sum;
}
int main()
{
	int m, n;
	cin >> m >> n;
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> arr[i][j];
		}
	}
	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			for (int k = 1; k <= m; k++)
			{
				for (int l = j + 1; l <= n; l++)//防止点重合
				{
					dp[i][j][k][l] = maxx(dp[i][j - 1][k - 1][l], dp[i][j - 1][k][l - 1], dp[i - 1][j][k][l - 1], dp[i - 1][j][k - 1][l]) + arr[i][j] + arr[k][l];
				}
			}
		}
	}
	cout << dp[m][n - 1][m - 1][n];//输出最终答案
	return 0;
}

【洛谷】【动态规划】P1006:传纸条(C/C++),洛谷,动态规划,c语言,c++,算法文章来源地址https://www.toymoban.com/news/detail-846049.html

到了这里,关于【洛谷】【动态规划】P1006:传纸条(C/C++)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 《算法导论》学习(十八)----动态规划之矩阵链乘(C语言)

    本文主要讲解了动态规划中的矩阵链乘问题:给定一个矩阵链,得到它的最小代价计算次序。给出了动态规划方案的分析,并且给出了C语言实现。 给定一个n个矩阵的序列(矩阵链) A 1 , A 2 , A 3 , A 4 , . . . , A n A_1,A_2,A_3,A_4,...,A_n A 1 ​ , A 2 ​ , A 3 ​ , A 4 ​ , ... , A n ​ ,现在

    2024年02月06日
    浏览(47)
  • 动态规划算法解决背包问题,算法分析与C语言代码实现,时间效率解析

    🎊【数据结构与算法】专题正在持续更新中,各种数据结构的创建原理与运用✨,经典算法的解析✨都在这儿,欢迎大家前往订阅本专题,获取更多详细信息哦🎏🎏🎏 🪔本系列专栏 -  数据结构与算法_勾栏听曲_0 🍻欢迎大家  🏹  点赞👍  评论📨  收藏⭐️ 📌个人主

    2023年04月16日
    浏览(50)
  • 贪心算法解决背包问题和动态规划解决0-1背包问题(c语言)

    运行结果如下: 运行结果如下: 总结: 贪心算法: 每一步都做出当时看起来最佳的选择,也就是说,它总是做出局部最优的选择。 贪心算法的设计步骤: 对其作出一个选择后,只剩下一个子问题需要求解。 证明做出贪心选择后,原问题总是存在最优解,即贪心选择总是安

    2024年02月04日
    浏览(56)
  • 最大子段和——用蛮力算法,分治策略,动态规划算法三种求法(C语言)

    目录 一、题目 二、算法求解 1、蛮力算法 伪代码  算法分析 程序 2、分治策略 伪代码 算法分析 程序 3、动态规划算法 伪代码 算法分析 程序 设A=a1,a2,...,an是n个整数的序列,称ai,....,aj为该序列的连续子序列,其中1=i=j=n,子序列的元素之和称为A的子段和: 例如,A=-2,11,-4,1

    2024年01月24日
    浏览(56)
  • 【洛谷 P4017】最大食物链计数 题解(深度优先搜索+动态规划+邻接表+记忆化搜索+剪枝)

    你知道食物链吗?Delia 生物考试的时候,数食物链条数的题目全都错了,因为她总是重复数了几条或漏掉了几条。于是她来就来求助你,然而你也不会啊!写一个程序来帮帮她吧。 给你一个食物网,你要求出这个食物网中最大食物链的数量。 (这里的“最大食物链”,指的

    2024年04月15日
    浏览(31)
  • 【算法】动态规划 ⑧ ( 动态规划特点 )

    求解类型 : 动态规划 必须是求 最值 , 可行性 , 方案数 , 三者之一 , 如果求其它内容 , 则不能使用动态规划算法 ; 求最值 : 最大值 , 最小值 等 ; 大规模问题的结果 由 小规模问题 的计算结果 取最大值 大规模问题的结果 由 小规模问题 的计算结果 取最小值 可行性 : 是否可行

    2023年04月08日
    浏览(48)
  • 【算法 - 动态规划】原来写出动态规划如此简单!

    从本篇开始,我们就正式开始进入 动态规划 系列文章的学习。 本文先来练习两道通过 建立缓存表 优化解题过程的题目,对如何将 递归函数 修改成 动态规划 的流程有个基本的熟悉。 用最简单的想法完成题目要求的 递归 函数; 定义明确 递归函数 的功能!!! 分析是否存

    2024年02月21日
    浏览(48)
  • 60题学会动态规划系列:动态规划算法第三讲

    简单多状态问题 文章目录 一.按摩师 二.打家劫舍系列 三.删除并获得点数 四.粉刷房子 力扣链接:力扣 一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。给定一个预约请求序列,

    2024年02月08日
    浏览(49)
  • 【算法】动态规划 ① ( 动态规划简介 | 自底向上的动态规划示例 | 自顶向下的动态规划示例 )

    动态规划 , 英文名称 Dynamic Programming , 简称 DP , 不是具体的某种算法 , 是一种算法思想 ; 具体的算法都有具体的步骤 , 如 : 二分法 , 其 有固定的解决步骤 , 先取一个中心点 , 判断解在左边还是右边 , 然后在一边再取一个中心点 , 再进行判定 , 该算法有具体的步骤 ; 动态规划

    2024年01月16日
    浏览(46)
  • 60题学会动态规划系列:动态规划算法第四讲

    买卖股票相关的动态规划题目 文章目录 1. 买卖股票的最佳时机含冷冻期 2. 买卖股票的最佳时期含⼿续费 3. 买卖股票的最佳时机III 4. 买卖股票的最佳时机IV 力扣链接:力扣 给定一个整数数组 prices ,其中第    prices[i]  表示第  i  天的股票价格 。​ 设计一个算法计算出最

    2024年02月13日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包