【Acwing1027】方格取数(动态规划)题解
题目描述
思路分析
错误思路:
贪心法,先走一次求出最大值,把走过的路上面的数值清零,然后用同样的方法再走一遍求最大值,然后让这两个最大值相加就是最后的结果。
很多人在看到这个题目的时候会有上面的思路,但实践告诉我们,有些数据用上述思路答案是错误的,这是为什么呢?
原因很简单:假设第一次走的时候,有多条路径s1,s2,......可以得到最大值,我们并不知道要选择哪一条,也就是说我们并不知道要把哪一条路上面的数清零,因为不同的选择会对第二次走的结果产生影响!!!
所以要使用其它思路,此处采用动态规划解决
起初,我们很容易想到用四维数组表示状态f[i1][j1][i2][j2]
但其实没有必要,因为我们只需要两条路“同时走”就可以了,也就是说我们可以设置一个维度代表(x,y方向上已经走的路径的和),这个表示为k,那么状态就可以降成三维:f[k][i1][i2]
下面对集合进行划分:
对于f[k][i1][i2],包含四部分:
第一部分是第一条路从上边走过来,第二条路是从上面走过来 f[k-1][i1-1][i2-1]+t
第二部分是第一条路从右边走过来,第二条路是从上面走过来 f[k-1][i1][i2-1]+t
第三部分是第一条路从上边走过来,第二条路是从右面走过来 f[k-1][i1-1][i2]+t
第四部分是第一条路从右边走过来,第二条路是从右面走过来 f[k-1][i1][i2]+t
那么这个t,怎么求,就要看i1和i2是否相同了,因为如果相同的话,再走到这里值已经清空了:
i1==i2 t=w[i1][k-i1]
i1!=i2 t=w[i1][k-i1]+w[i2][k-i2]
最后答案即为:f[n+n][n][n]
#include<iostream>
using namespace std;
const int N=15;
int f[N*2][N][N];
int w[N][N];
int n;
int main()
{scanf("%d",&n);int a,b,c;while(cin>>a>>b>>c,a||b||c)w[a][b]=c;for(int k=2;k<=n*2;k++){for(int i1=1;i1<=n;i1++){for(int i2=1;i2<=n;i2++){int j1=k-i1,j2=k-i2;if(j1>=1&&j1<=n&&j2>=1&&j2<=n){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-1][i2-1]+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][i2]+t);}}}}cout<<f[2*n][n][n];return 0;
}
相关文章:

【Acwing1027】方格取数(动态规划)题解
题目描述 思路分析 错误思路: 贪心法,先走一次求出最大值,把走过的路上面的数值清零,然后用同样的方法再走一遍求最大值,然后让这两个最大值相加就是最后的结果。 很多人在看到这个题目的时候会有上面的思路&#x…...
合并区间:解决区间重叠问题的高效算法
合并区间:解决区间重叠问题的高效算法 leetcode 56. 合并区间 合并区间是一个常见的编程问题,通常涉及到一组区间,你需要将重叠的区间合并成更大的区间。这篇博客将介绍这个问题的背景,然后解释一个高效的解决方案,同…...

万字总结HTML超文本标记语言
一、前言:什么是网页? 网站是指在因特网上根据一定的规则,使用 HTML 等制作的用于展示特定内容相关的网页集合。网页是网站中的一“页”,通常是 HTML 格式的文件,它要通过浏览器来阅读。 网页是构成网站的基本元素,它通常由图片、链接、文字、声音、视频等元素组成。通常…...

Java线程池是如何保证核心线程不被销毁的
来源: Java线程池是如何保证核心线程不被销毁的_朝 花 拾 夕的博客-CSDN博客 对于Java中 Thread 对象,同一个线程对象调用 start 方法后,会在执行完run 后走向终止(TERMINATED)状态,也就是说一个线程对象是不可以通过多…...
新课程标准培养学生“高考物理关键能力”的实践研究课题文献综述
目录 一、高考物理能力的要求与评估标准 二、高考物理关键能力的定义与内涵...

急救车工业路由器应用提升急救效率:车联网、数据采集与远程诊疗
急救车作为医院里医疗急救过程中的重要组成部分,在智慧医疗物联网领域中急救车应用4G工业路由器实现网络部署与数据采集,通过工业4G路由器能够实时采集到病患的生理数据、救护现场音频与视频、GPS定位以及车辆运行状态等重要信息。这些数据将被传输到医疗…...
【操作系统】聊聊CPU上下文切换实操
如何查看系统的上下文切换情况 上一篇文章我们说了过多的上下文切换,会把CPU时间消耗在寄存器、内核栈以及虚拟内存等数据的保存和恢复上,那么当出现系统的上下文切换过多的时候,我们如果通过监控指标查看呢。 vmstat 是一个常用的系统性能…...

【java】【SpringBoot】【四】原理篇 bean、starter、核心原理
目录 一、自动配置 1、bean加载方式(复习) 1.1 加载方式-xml方式生命bean 1.2 加载方式-xml注解方式声明bean 1.3 注解方式声明配置类 1.4 FactoryBean 1.5 proxyBeanMethod属性 1.6 使用Import注解导入 1.7 使用上下文对象在容器初始化完毕后注…...

【精品资源】Java毕业设计攻略:从选题到答辩,一站式指南
导读: Java毕业设计是计算机科学与技术专业学生展示其编程能力、问题解决能力和创新思维的重要环节。这篇博客将为您提供一站式的Java毕业设计攻略,帮助您从选题到答辩,顺利完成毕业设计。 一、选题阶段 寻找灵感: 探讨热门技术如…...

文件高效批量重命名,轻松重命名不同类型的文件名并隐藏编号
你是否曾经因为文件名混乱而感到困扰?你是否希望有一种方法可以快速、简单地管理你的文件名?如果你的答案是肯定的,那么我们的产品——文件重命名工具,将是你的完美解决方案! 首先我们要进入文件批量改名高手主页面&a…...

接口的定义与实现
一个c,代表类(class)。 一个c再加上两竖线,代表抽象类。 一个i,代表接口(interface)。 package com.mypackage.oop.demo12;//接口都需要有一个实现类 public interface UserService {//接口中定…...

浅谈低压绝缘监测及定位系统在海上石油平台的研究与应用
安科瑞 华楠 摘要:海上石油平台低压系统与陆地电力系统有很大区别,其属于中性点绝缘系统,在出现单相接地故障时,系统允许带故障正常运行2 h,保证海上重要电气设备不会立即关停。现以渤海某海上平台为例,其…...

Java项目:SSM的食堂点餐系统
作者主页:Java毕设网 简介:Java领域优质创作者、Java项目、学习资料、技术互助 文末获取源码 一、相关文档 系统中的核心用户是系统管理员,管理员登录后,通过管理员菜单来管理后台系统。主要功能有:个人中心、用户管理…...

Linux桌面环境中应用程序无法启动图形交互界面
现象: 点击永中office或者金山office快捷图标无法启动对应的程序。 从命令行执行对应的程序则提示 按照提示安装组件 再次执行命令行程序 原因探析: /opt/Yozosoft/Yozo_Office/Yozo_Writer.bin: error while loading shared libraries: libgdk-x11-2.0.…...

jupyter notebook进不去指定目录怎么办?
首先激活你要使用的虚拟环境 刚开始是现在 (base) C:\Users\lenovo>目录下 直接输入你想进入的盘 (base) C:\Users\lenovo>e:此时再cd (base) C:\Users\lenovo>cd E:\tim\learn_pytorch 就可以进入了 安装3.4.1.15问题 已经有了最新python版本的虚拟环境&#…...

MySQL 高级(进阶) SQL 语句(二) -----存储过程
目录 1 存储过程 1.1 创建存储过程 1.2 调用存储过程 1.3 查看存储过程 1.4 存储过程的参数 1.5 修改存储过程 1.6 删除存储过程 2 条件语句 3 循环语句 1 存储过程 存储过程是一组为了完成特定功能的SQL语句集合。 存储过程在使用过程中是将常用或者复杂的工作预…...

机器学习第十三课--主成分分析PCA
一.高维数据 除了图片、文本数据,我们在实际工作中也会面临更多高维的数据。比如在评分卡模型构建过程中,我们通常会试着衍生出很多的特征,最后就得到上千维、甚至上完维特征;在广告点击率预测应用中,拥有几个亿特征也是常见的事…...

钉钉stream机器人-实操详细教程
支持事件订阅、机器人收消息、卡片回调等功能 优点: 配置简单,不依赖也不需要暴露公网IP,无需向公网开放端口 github官方链接:GitHub - open-dingtalk/dingtalk-stream-sdk-python: Python SDK for DingTalk Stream Mode API, Co…...
设计模式:访问者模式(C++实现)
访问者模式通过将对元素的操作与元素本身分离,使得可以在不修改元素类的情况下定义新的操作。 #include <iostream> #include <vector> #include <algorithm>// 前向声明 class ConcreteElementA; class ConcreteElementB;// 访问者接口 class V…...
Pygame中Sprite的使用方法6-6
4 重新绘制界面 每次碰撞发生后,程序界面需要重新绘制,代码如下所示。 screen.fill(WHITE) all_sprites_list.draw(screen) pygame.display.flip() 其中,screen表示程序的整个界面,将其绘制为白色背景;之后通过all_…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...

第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...

.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...

大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...