当前位置: 首页 > 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_…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...