动态规划数字三角形模型——AcWing 275. 传纸条

动态规划数字三角形模型

定义

动态规划数字三角形模型是在一个三角形的数阵中,通过一定规则找到从顶部到底部的最优路径或最优值。

运用情况

通常用于解决具有递推关系、需要在不同路径中做出选择以达到最优结果的问题。比如计算最短路径、最大和等。

计算其他类型的最优值。比如,要求找到从顶部到底部路径上数字乘积最大,或者找到具有某种特定属性(如奇数个数最多等)的最优路径。

注意事项

  • 状态定义的准确性:要仔细分析问题,选择最能简洁且准确反映问题本质的状态表示。如果定义不当,可能导致后续递推关系复杂或无法正确求解。
  • 边界条件的多样性:不同问题的边界条件可能不同,比如三角形顶部的状态初始化,或者边缘位置的特殊处理等。
  • 递推关系的严谨性:需要充分考虑各种可能情况,确保递推关系涵盖了所有可能的决策和状态转移。

解题思路

  • 在确定状态时,有时可能需要结合一些额外的信息,比如记录路径本身或其他相关属性。
  • 递推关系的建立可能需要综合考虑多个因素,甚至可能引入辅助数组或变量来辅助计算。
  • 对于复杂的数字三角形问题,可能需要分阶段或分层进行递推计算,逐步逼近最终的最优解。

例如,在一个更复杂的数字三角形中,除了数字本身,每个位置还有一个权重,要求在权重限制下找到最大和。这时状态可能需要扩展为 dp[i][j][k] 表示到达第 i 行第 j 列且当前权重为 k 时的最大和,递推关系也会相应变得更加复杂。通过这样的细致分析和设计,可以更好地运用动态规划数字三角形模型解决各种实际问题。

AcWing 275. 传纸条

题目描述

275. 传纸条 - AcWing题库

运行代码

#include <iostream>
#include <cstring>
using namespace std;
int w[60][60], f[60*60][60][60];
void run()
{int n, m;cin >> n >> m;int a, b, c;for(int i = 1; i <= n; i ++)for(int j = 1; j <= m; j ++)cin >> w[i][j];for(int k = 2; k <= n + m; k ++)for(int i1 = max(1, k - m); i1 <= n && i1 < k; i1 ++)for(int i2 = max(1, k - m); i2 <= n && i2 < k; i2 ++){int j1 = k - i1, j2 = k - i2;if(j1 >= 1 && j1 <= m && j2 >= 1 && j2 <= m){int t = w[i1][j1];if(i1 != i2) t += w[i2][j2];int &x = f[k][i1][i2];x = max(x, f[k - 1][i1][i2] + t);x = max(x, f[k - 1][i1 - 1][i2] + t);x = max(x, f[k - 1][i1][i2 - 1] + t);x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);}}cout << f[n + m][n][n] << endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);run();return 0;
}

代码思路

  • 定义了二维数组 w 来存储每个位置的好感度值。
  • f[k][i1][i2] 这个三维数组用于记录在特定阶段(即走了 k 步时),从左上角到点 (i1, j1) 和从左上角到点 (i2, j2) (其中 j1 = k - i1j2 = k - i2)两条路径所能获得的最大好感度和。
  • 通过三重循环遍历不同的位置和阶段。对于每个阶段 k 和对应的两个位置 i1i2,计算当前状态下能获得的好感度值,并与之前的状态进行比较更新。具体更新时,考虑从四个可能的方向(上一步是 i1 不变 i2 不变、i1 减 1 i2 不变、i1 不变 i2 减 1、i1 减 1 i2 也减 1)转移过来的情况,取最大值进行更新。
  • 最后输出 f[n + m][n][n],即走完整个矩阵从左上角到右下角且两条路径都到达右下角时的最大好感度和。

改进思路

  • 可以考虑添加一些必要的注释提高代码的可读性。
  • 对于一些重复的代码逻辑,可以考虑提取成函数来提高代码的简洁性和可维护性。

改进代码

#include <iostream>
#include <cstring>
using namespace std;
int w[60][60], f[60*60][60][60];
void updateMax(int k, int i1, int i2, int j1, int j2, int t) {int& x = f[k][i1][i2];x = max(x, f[k - 1][i1][i2] + t);x = max(x, f[k - 1][i1 - 1][i2] + t);x = max(x, f[k - 1][i1][i2 - 1] + t);x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
}
void run() {int n, m;cin >> n >> m;int a, b, c;for(int i = 1; i <= n; i ++)for(int j = 1; j <= m; j ++)cin >> w[i][j];for(int k = 2; k <= n + m; k ++) {for(int i1 = max(1, k - m); i1 <= n && i1 < k; i1 ++) {for(int i2 = max(1, k - m); i2 <= n && i2 < k; i2 ++) {int j1 = k - i1, j2 = k - i2;if(j1 >= 1 && j1 <= m && j2 >= 1 && j2 <= m) {int t = w[i1][j1];if(i1!= i2) t += w[i2][j2];updateMax(k, i1, i2, j1, j2, t);}}}}cout << f[n + m][n][n] << endl;
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);run();return 0;
}

其它代码

#include <iostream>using namespace std;const int N = 60;int n, m;
int a[N][N];
int f[N * 2][N][N];int main()
{cin >> n >> m;for(int i = 1; i <= n; i ++ )for(int j = 1; j <= m; j ++ )cin >> a[i][j];for(int k = 2; k <= n + m; k ++ )for(int x1 = 1; x1 <= n; x1 ++ )for(int x2 = 1; x2 <= n; x2 ++ ){int y1 = k - x1, y2 = k - x2;int t = a[x1][y1];if(y1 >= 1 && y1 <= m && y2 >= 1 && y2 <= m){if(x1 != x2 || k == 2 || k == n + m){t += a[x2][y2];int &c = f[k][x1][x2];c = max(c, f[k - 1][x1][x2] + t);c = max(c, f[k - 1][x1 - 1][x2] + t);c = max(c, f[k - 1][x1][x2 - 1] + t);c = max(c, f[k - 1][x1 - 1][x2 - 1] + t);}}}cout << f[n + m][n][n] << endl;return 0;
}

代码思路

  • 定义了常量 N 表示矩阵的最大规模。
  • 输入矩阵的行数 n 和列数 m,并读取矩阵元素值到 a 数组。
  • f[k][x1][x2] 这个三维数组用于记录某种状态下的最优值。
  • 通过三重循环遍历不同的阶段(由 k 表示)以及两个位置 x1 和 x2。根据当前的行坐标计算出对应的列坐标 y1 和 y2
  • 只有当两个位置对应的列坐标都在合法范围内时,进行计算。如果满足特定条件(比如两个位置不同或者是边界情况),计算当前的好感度值 t(包含两个位置的元素值),然后更新 f[k][x1][x2] 的值,通过与之前阶段的各种可能情况的最优值进行比较取最大值。
  • 最后输出最终状态下 f[n+m][n][n] 的值。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/360173.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

服务器数据恢复—NTFS文件系统下双循环riad5数据恢复案例

服务器存储数据恢复环境&#xff1a; EMC CX4-480存储&#xff0c;该存储中有10块硬盘&#xff0c;其中有3块磁盘为掉线磁盘&#xff0c;另外7块磁盘组成一组RAID5磁盘阵列。运维人员在处理掉线磁盘时只添加新的硬盘做rebuild&#xff0c;并没有将掉线的硬盘拔掉&#xff0c;所…

重点!业内分享:如何找到自己门店的生鲜经营定位

说到经营生鲜品类 许多商超人士或许都会面临这样一个困境 即品类繁多且复杂&#xff0c;那么如何做到精准施策&#xff1f; 比如说&#xff0c;蔬菜和水果虽都归为生鲜&#xff0c;然而细分起来&#xff0c;价格和消费群体均存在差异。像蔬菜&#xff0c;价格通常较低&#…

docker入门配置

1、创建配置镜像 由于国内docker连接外网速度慢&#xff0c;采用代理 vi /etc/docker/daemon.json添加以下内容 {"registry-mirrors": ["https://9cpn8tt6.mirror.aliyuncs.com","https://dockerproxy.com","https://hub-mirror.c.163.co…

Python开发日记--手撸加解密小工具(2)

目录 1. UI设计和代码生成 2.运行代码查看效果 3.小结 1. UI设计和代码生成 昨天讨论到每一类算法设计为一个Tab&#xff0c;利用的是TabWidget&#xff0c;那么接下来就要在每个Tab里设计算法必要的参数了&#xff0c;这里我们会用到组件有Label、PushButton、TextEdit、Ra…

第4讲:pixi.js绘制舞台、随窗口大小而改变画布大小和舞台位置

基于前面写的代码&#xff0c;在gamelets的工程目录下新建一个CanvasAndStage.ts 代码如下 import {Application, Graphics} from pixi.js; // 不要忘了&#xff0c;一定要引用这个css样式&#xff0c;否则就会以默认样式显示 import ./style.css // app.view就是画布&#xf…

使用JAVA代码实现发送订阅消息以及模板消息

今天写了一个商品到货提醒的job任务&#xff0c;具体效果如下 这里用到了微信的发送订阅消息&#xff0c;主要代码是这一块的&#xff0c;最后我把发送了消息的订单存到表里&#xff0c;因为是定时任务&#xff0c;大家可不存 发送订阅消息 | 微信开放文档 /*** 微信平台-商品…

<电力行业> - 《第1课:电力行业的五大四小》

1 什么是电力行业的五大四小&#xff1f; 我们常说的电力行业的五大四小&#xff0c;指的是电力行业有实力的公司&#xff0c;分为&#xff1a;较强梯队的五大集团、较弱梯队的四小豪门。 五个实力雄厚的集团&#xff0c;分别是&#xff1a; 中国华能集团公司中国大唐集团公…

公交行业系统特点及面临的挑战

在当前城市发展中&#xff0c;公交行业作为公共交通的重要组成部分&#xff0c;承担着重要的社会责任。随着科技的进步和城市化进程的加快&#xff0c;公交行业系统也在不断地发展和完善。然而&#xff0c;从目前的发展情况来看&#xff0c;公交行业系统也呈现出一些显著的特点…

怎么加密文件夹?文件夹加密软件推荐

文件夹加密是保护电脑数据的重要方法&#xff0c;那么你知道怎么加密文件夹吗&#xff1f;下面小编就为大家推荐两款文件夹加密软件&#xff0c;帮助你安全保护重要文件夹。 文件夹加密超级大师 在加密电脑文件夹时&#xff0c;文件夹加密超级大师是你必须要了解的文件夹加密软…

uniapp顶部导航栏实现自定义功能按钮+搜索框并监听响应事件

目录 第一步&#xff1a;先下载按钮需要展示的图标&#xff08;若不使用图标&#xff0c;直接使用文字可跳过这步&#xff09; 1、点击需要的图标&#xff0c;添加入库 2、点击旁边的购物车&#xff0c;在弹出的窗口中选择下载代码 3、解压下载的压缩包&#xff0c;将这几个…

鸿蒙 HarmonyOS NEXT星河版APP应用开发-阶段二

一、鸿蒙应用界面开发 弹性布局-Flex 语法 /* 弹性容器组件 Flex() 位置&#xff1a; Flex默认主轴水平往右&#xff0c;交叉轴垂直向下&#xff08;类似Row&#xff09; 语法&#xff1a; Flex(参数对象){子组件1,子组件2,子组件3 } 属性方法&#xff1a; direction&#xf…

Hi3861 OpenHarmony嵌入式应用入门--轮询按键

本篇介绍使用轮询方式读取gpio状态来判断按键状态。 原理图如下 GPIO API API名称 说明 hi_u32 hi_gpio_init(hi_void); GPIO模块初始化 hi_u32 hi_io_set_pull(hi_io_name id, hi_io_pull val); 设置某个IO上下拉功能。 hi_u32 hi_gpio_set_dir(hi_gpio_idx id, hi_gpi…

达梦数据库(DM8)替换授权dm.key遇到的错误, lic info is different between dm.key and sysinfo.

1、报错贴图 2、报错日志提示 version info: security lic info is different between dm.key and sysinfo. 原因说明&#xff1a;dm.key授权与服务器的硬件环境不匹配引起的报错&#xff0c;如&#xff1a;cpu、操作系统版本有关。

高通安卓12-安卓系统定制2

将开机动画打包到system.img里面 在目录device->qcom下面 有lito和qssi两个文件夹 现在通过QSSI的方式创建开机动画&#xff0c;LITO方式是一样的 首先加入自己的开机动画&#xff0c;制作过程看前面的部分 打开qssi.mk文件&#xff0c;在文件的最后加入内容 PRODUCT_CO…

嘀嗒出行项目管理专家和项目管理负责人王禹华受邀为第十三届中国PMO大会演讲嘉宾

全国PMO专业人士年度盛会 嘀嗒出行项目管理专家和项目管理负责人王禹华女士受邀为第十三届中国PMO大会演讲嘉宾&#xff0c;演讲议题为“AI时代项目经理挑战机会和个人成长”。大会将于6月29-30日在北京举办&#xff0c;敬请关注&#xff01; 议题简要&#xff1a; AI时代对互…

智能雷达在线编辑名片小程序源码系统 前后端分离 带完整的安装代码包以及搭建教程

系统概述 智能雷达在线编辑名片小程序源码系统是一款集创新性、实用性和便捷性于一体的工具。它采用前后端分离的架构&#xff0c;为用户提供了一个强大的平台&#xff0c;可用于创建、编辑和管理个性化名片。 该系统旨在满足现代商业和社交需求&#xff0c;提供了一种高效、…

高校新生如何选择最优手机流量卡?

一年一度的高考已经结束了&#xff0c;愿广大学子金榜题名&#xff0c;家长们都给孩子准备好了手机&#xff0c;那么手机流量卡应该如何选择呢&#xff1f; 高校新生在选择手机流量卡时&#xff0c;需要综合考量流量套餐、费用、网络覆盖、售后服务等多方面因素&#xff0c;以下…

如何选择和优化谷歌外贸关键词?

长尾关键词是关键&#xff0c;长尾关键词是指由三个或更多词组成的更具体、更详细的搜索词组。与单个关键词相比&#xff0c;长尾关键词虽然搜索量较低&#xff0c;但往往能带来更高的转化率&#xff0c;因为它们更能精准地反映用户的搜索意图和需求 使用长尾关键词有几个优势…

全国计算机等级考试WPS如何报名

全国计算机等级考试WPS如何报名&#xff1f; 注册并登录 全国计算机等级考试官网选择 考试服务-在线报名选择报考省份-开始报名

qt经典界面框架

目的 其实就是一个简单的界面显示&#xff0c;是很常用的形式。 说起来简单也是简单&#xff0c;但当初&#xff0c;刚开始做时&#xff0c;感觉非常的复杂&#xff0c;不知如何下手。 现在感觉简单多了。 这个框架利用了QT的现成的MainWindow与QDockWidget&#xff0c;这样就…