当前位置: 首页 > news >正文

【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】方格取数(动态规划)题解

题目描述 思路分析 错误思路&#xff1a; 贪心法&#xff0c;先走一次求出最大值&#xff0c;把走过的路上面的数值清零&#xff0c;然后用同样的方法再走一遍求最大值&#xff0c;然后让这两个最大值相加就是最后的结果。 很多人在看到这个题目的时候会有上面的思路&#x…...

合并区间:解决区间重叠问题的高效算法

合并区间&#xff1a;解决区间重叠问题的高效算法 leetcode 56. 合并区间 合并区间是一个常见的编程问题&#xff0c;通常涉及到一组区间&#xff0c;你需要将重叠的区间合并成更大的区间。这篇博客将介绍这个问题的背景&#xff0c;然后解释一个高效的解决方案&#xff0c;同…...

万字总结HTML超文本标记语言

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

Java线程池是如何保证核心线程不被销毁的

来源: Java线程池是如何保证核心线程不被销毁的_朝 花 拾 夕的博客-CSDN博客 对于Java中 Thread 对象&#xff0c;同一个线程对象调用 start 方法后&#xff0c;会在执行完run 后走向终止&#xff08;TERMINATED&#xff09;状态&#xff0c;也就是说一个线程对象是不可以通过多…...

新课程标准培养学生“高考物理关键能力”的实践研究课题文献综述

目录 一、高考物理能力的要求与评估标准 二、高考物理关键能力的定义与内涵...

急救车工业路由器应用提升急救效率:车联网、数据采集与远程诊疗

急救车作为医院里医疗急救过程中的重要组成部分&#xff0c;在智慧医疗物联网领域中急救车应用4G工业路由器实现网络部署与数据采集&#xff0c;通过工业4G路由器能够实时采集到病患的生理数据、救护现场音频与视频、GPS定位以及车辆运行状态等重要信息。这些数据将被传输到医疗…...

【操作系统】聊聊CPU上下文切换实操

如何查看系统的上下文切换情况 上一篇文章我们说了过多的上下文切换&#xff0c;会把CPU时间消耗在寄存器、内核栈以及虚拟内存等数据的保存和恢复上&#xff0c;那么当出现系统的上下文切换过多的时候&#xff0c;我们如果通过监控指标查看呢。 vmstat 是一个常用的系统性能…...

【java】【SpringBoot】【四】原理篇 bean、starter、核心原理

目录 一、自动配置 1、bean加载方式&#xff08;复习&#xff09; 1.1 加载方式-xml方式生命bean 1.2 加载方式-xml注解方式声明bean 1.3 注解方式声明配置类 1.4 FactoryBean 1.5 proxyBeanMethod属性 1.6 使用Import注解导入 1.7 使用上下文对象在容器初始化完毕后注…...

【精品资源】Java毕业设计攻略:从选题到答辩,一站式指南

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

文件高效批量重命名,轻松重命名不同类型的文件名并隐藏编号

你是否曾经因为文件名混乱而感到困扰&#xff1f;你是否希望有一种方法可以快速、简单地管理你的文件名&#xff1f;如果你的答案是肯定的&#xff0c;那么我们的产品——文件重命名工具&#xff0c;将是你的完美解决方案&#xff01; 首先我们要进入文件批量改名高手主页面&a…...

接口的定义与实现

一个c&#xff0c;代表类&#xff08;class&#xff09;。 一个c再加上两竖线&#xff0c;代表抽象类。 一个i&#xff0c;代表接口&#xff08;interface&#xff09;。 package com.mypackage.oop.demo12;//接口都需要有一个实现类 public interface UserService {//接口中定…...

浅谈低压绝缘监测及定位系统在海上石油平台的研究与应用

安科瑞 华楠 摘要&#xff1a;海上石油平台低压系统与陆地电力系统有很大区别&#xff0c;其属于中性点绝缘系统&#xff0c;在出现单相接地故障时&#xff0c;系统允许带故障正常运行2 h&#xff0c;保证海上重要电气设备不会立即关停。现以渤海某海上平台为例&#xff0c;其…...

Java项目:SSM的食堂点餐系统

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

Linux桌面环境中应用程序无法启动图形交互界面

现象&#xff1a; 点击永中office或者金山office快捷图标无法启动对应的程序。 从命令行执行对应的程序则提示 按照提示安装组件 再次执行命令行程序 原因探析&#xff1a; /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

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

钉钉stream机器人-实操详细教程

支持事件订阅、机器人收消息、卡片回调等功能 优点&#xff1a; 配置简单&#xff0c;不依赖也不需要暴露公网IP&#xff0c;无需向公网开放端口 github官方链接&#xff1a;GitHub - open-dingtalk/dingtalk-stream-sdk-python: Python SDK for DingTalk Stream Mode API, Co…...

设计模式:访问者模式(C++实现)

访问者模式通过将对元素的操作与元素本身分离&#xff0c;使得可以在不修改元素类的情况下定义新的操作。 #include <iostream> #include <vector> #include <algorithm>// 前向声明 class ConcreteElementA; class ConcreteElementB;// 访问者接口 class V…...

Pygame中Sprite的使用方法6-6

4 重新绘制界面 每次碰撞发生后&#xff0c;程序界面需要重新绘制&#xff0c;代码如下所示。 screen.fill(WHITE) all_sprites_list.draw(screen) pygame.display.flip() 其中&#xff0c;screen表示程序的整个界面&#xff0c;将其绘制为白色背景&#xff1b;之后通过all_…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

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

.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过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...