1027. 方格取数

Powered by:NEFU AB-IN

Link

文章目录

  • 1027. 方格取数
    • 题意
    • 思路
    • 代码

1027. 方格取数

  • 题意

某人从图中的左上角 A 出发,可以向下行走,也可以向右行走,直到到达右下角的 B 点。

在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字0)。

此人从 A 点到 B 点共走了两次,试找出两条这样的路径,使得取得的数字和为最大。

  • 思路

典型的数字三角形模型的dp,但是不是走一遍,而是走两遍。此时不能贪心的做,做一遍dp,再做一遍dp
题目应该等价于,两个人同时走
思路为再加一维的dp,记录两人的总步数,这样三维dp,就会分为四种情况,而不是之前的两个情况(由上和左走过来)

具体思路如下图
在这里插入图片描述

  • 代码

# import
from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque, defaultdict
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, gcd, sqrt, fabs, ceil, floor
from types import GeneratorType
from typing import TypeVar, List, Dict, Any, Callable# Data structure
class SA:def __init__(self, x, y):self.x = xself.y = ydef __lt__(self, other):return self.x < other.x# Constants
N = int(20)  # If using AR, modify accordingly
M = int(20)
INF = int(2e9)# Set recursion limit
setrecursionlimit(INF)# Read
input = lambda: stdin.readline().rstrip("\r\n")  # Remove when Mutiple data
read = lambda: map(int, input().split())
read_list = lambda: list(map(int, input().split()))# Func
class std:# Recursion@staticmethoddef bootstrap(f, stack=None):if stack is None:stack = []def wrappedfunc(*args, **kwargs):if stack:return f(*args, **kwargs)else:to = f(*args, **kwargs)while True:if isinstance(to, GeneratorType):stack.append(to)to = next(to)else:stack.pop()if not stack:breakto = stack[-1].send(to)return toreturn wrappedfuncletter_to_num = staticmethod(lambda x: ord(x.upper()) - 65)  # A -> 0num_to_letter = staticmethod(lambda x: ascii_uppercase[x])  # 0 -> Aarray = staticmethod(lambda x=0, size=N: [x] * size)array2d = staticmethod(lambda x=0, rows=N, cols=M: [std.array(x, cols) for _ in range(rows)])max = staticmethod(lambda a, b: a if a > b else b)min = staticmethod(lambda a, b: a if a < b else b)filter = staticmethod(lambda func, iterable: list(filter(func, iterable)))# —————————————————————Division line ——————————————————————n, = read()
w = std.array2d(0, N, N)
f = [std.array2d(0, N, N) for _ in range(N * 2)]while True:x, y, num = read()if x + y + num == 0:breakw[x][y] = numfor k in range(2, n + n + 1):for i1 in range(1, n + 1):for i2 in range(1, n + 1):j1 = k - i1j2 = k - i2if 1 <= j1 <= n and 1 <= j2 <= n:t = w[i1][j1]if i1 != i2:t += w[i2][j2]f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2 - 1] + t,f[k - 1][i1 - 1][i2] + t,f[k - 1][i1][i2 - 1] + t,f[k - 1][i1][i2] + t)print(f[n + n][n][n])

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

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

相关文章

Docker网络介绍

网络是虚拟化技术中最复杂的部分&#xff0c;也是Docker应用中的一个重要环节。 Docker中的网络主要解决容器与容器、容器与外部网络、外部网络与容器之间的互相通信的问题。 这些复杂情况的存在要求Docker有一个强大的网络功能去保障其网络的稳健性。因此&#xff0c;Docker…

SCI一区TOP|双曲正弦余弦优化算法(SCHO)原理及实现【免费获取Matlab代码】

目录 1.背景2.算法原理2.1算法思想2.2算法过程 3.结果展示4.参考文献5.代码获取 1.背景 2023年&#xff0c;J Bai受到双曲正弦余弦函数启发&#xff0c;提出了双曲正弦余弦优化算法&#xff08;Sinh Cosh optimizer, SCHO&#xff09;。 2.算法原理 2.1算法思想 SCHO灵感来源…

分布式锁(Redission)

分布式锁&#xff1a; 使用场景&#xff1a; 通常对于一些使用率高的服务&#xff0c;我们会进行多次部署&#xff0c;可能会部署在不同的服务器上&#xff0c;但是他们获取和操作的数据仍然是同一份。为了保证服务的强一致性&#xff0c;我们需要对线程进行加锁&#xff0c;…

ROS中的TF是什么

在ROS (Robot Operating System) 中&#xff0c;tf::TransformBroadcaster 是一个用于发布坐标变换信息的重要类&#xff0c;尤其在处理机器人定位和导航数据时非常常见。tf::TransformBroadcaster 对象允许你广播从一个坐标系到另一个坐标系的变换关系&#xff0c;这对于多传感…

Vue38 安装脚手架 vue-cli ,并使用脚手架创建项目

安装脚手架 vue-cli &#xff0c;并使用脚手架创建项目 第一步 安装脚手架 npm config set registry https:\\[registry.npmmirror.com // 切换淘宝镜像 npm install -g vue/cli第二步 切换到创建项目的目录&#xff0c;创建项目 cd XXX vue create XXX第三步 启动项目 npm…

【Linux】基础IO_3

文章目录 六、基础I/O3. 软硬链接4. 动静态库 未完待续 六、基础I/O 3. 软硬链接 使用 ln 就可以创建链接&#xff0c;使用 ln -s 可以创建软链接&#xff0c;直接使用 ln 则是硬链接。 我们对硬链接进行测试一下&#xff1a; 根据测试&#xff0c;我们知道了 硬链接就像一…

WPF文本绑定显示格式StringFormat设置-数值类型处理

绑定显示格式设置 在Textblock等文本控件中&#xff0c;我们经常要绑定一些数据类型&#xff0c;但是我们希望显示的时候能够按照我们想要的格式去显示&#xff0c;比如增加文本前缀&#xff0c;后面加单位&#xff0c;显示百分号等等&#xff0c;这种就需要对绑定格式进行处理…

天马学航——智慧教务系统(移动端)开发日志四

天马学航——智慧教务系统(移动端)开发日志四 日志摘要&#xff1a;优化了教师端界面的UI&#xff0c;更新了教师端添加课程&#xff0c;提交成绩等功能&#xff0c;修复了一些已知的BUG 1、教师添加课程设计 教师在此界面添加课程&#xff0c;并将数据提交后端进行审核 界…

Dell戴尔灵越Inspiron 16 Plus 7640/7630笔记本电脑原装Windows11下载,恢复出厂开箱状态预装OEM系统

灵越16P-7630系统包: 链接&#xff1a;https://pan.baidu.com/s/1Rve5_PF1VO8kAKnAQwP22g?pwdjyqq 提取码&#xff1a;jyqq 灵越16P-7640系统包: 链接&#xff1a;https://pan.baidu.com/s/1B8LeIEKM8IF1xbpMVjy3qg?pwdy9qj 提取码&#xff1a;y9qj 戴尔原装WIN11系…

python flask配置邮箱发送功能,使用flask_mail模块

&#x1f308;所属专栏&#xff1a;【Flask】✨作者主页&#xff1a; Mr.Zwq✔️个人简介&#xff1a;一个正在努力学技术的Python领域创作者&#xff0c;擅长爬虫&#xff0c;逆向&#xff0c;全栈方向&#xff0c;专注基础和实战分享&#xff0c;欢迎咨询&#xff01; 您的点…

Mamba: Linear-Time Sequence Modeling with Selective State Spaces论文笔记

文章目录 Mamba: Linear-Time Sequence Modeling with Selective State Spaces摘要引言 相关工作(SSMs)离散化计算线性时间不变性(LTI)结构和尺寸一般状态空间模型SSMs架构S4(补充)离散数据的连续化: 基于零阶保持技术做连续化并采样循环结构表示: 方便快速推理卷积结构表示: 方…

Vue80-全局路由守卫:前置、后置

一、路由守卫的定义 二、需求 在第三步&#xff0c;做校验&#xff01; 三、代码实现 3-1、前置路由守卫 注意&#xff0c;此时就不能将router一开始就暴露出去了&#xff01; to和from是路由组件的信息。 写法一&#xff1a; 写法二&#xff1a; 缺点&#xff1a;若是路由…

算法04 模拟算法之一维数组相关内容详解【C++实现】

大家好&#xff0c;我是bigbigli&#xff0c;模拟算法我们将分为几个章节来讲&#xff0c;今天我们只看一维数组相关的题目 目录 模拟的概念 训练&#xff1a;开关灯 解析 参考代码 训练&#xff1a;数组变化 解析 参考代码 训练&#xff1a;折叠游戏 解析 参考代码 …

动态ARP

定义 动态ARP表项由ARP协议通过ARP报文自动生成和维护&#xff0c;可以被老化&#xff0c;可以被新的ARP报文更新&#xff0c;可以被静态ARP表项覆盖。 动态ARP适用于拓扑结构复杂、通信实时性要求高的网络。 ARP地址解析过程 动态ARP通过广播ARP请求和单播ARP应答这两个过…

33 - 连续出现的数字(高频 SQL 50 题基础版)

33 - 连续出现的数字 -- 开窗函数lead(col,n) 统计窗口内往下第n行值 -- over(partition by xxx) 按照xxx所有行进行分组 -- over(partition by xxx order by aaa) 按照xxx分组&#xff0c;按照aaa排序select distinct num as ConsecutiveNums from(select num,# 从当前记录获…

运行vue3项目相关报错

1. VSCode打开TSVue3项目很多地方报错 报错内容 几乎所有文件都会出现未知飘红 error Delete CR prettier/prettier报错原因 插件冲突&#xff0c;Windows系统回车换行符与MAC不一致&#xff08;所以这个问题Windows系统才会出现&#xff09; 解决 需要安装Vue - Official…

永磁同步电机FOC调试记录(一)

永磁同步电机FOC调试记录&#xff08;一&#xff09; 前言架构硬件架构软件架构 调试过程元器件选型开环控制编码器调试速度采样电流检测中断优先级的确定电流环部分烧坏IPM速度-电流环位置-电流环 结语 前言 这是我个人从零开始尝试永磁同步电机&#xff08;PMSM&#xff09;…

【LeetCode刷题】232.用栈实现队列

目录 题目链接 图解思路 整体结构 实现过程 入队列 出队列 实现代码 MyQueue.h MyQueue.c stack.h stack.c test.c 题目链接 232. 用栈实现队列 - 力扣&#xff08;LeetCode&#xff09; 图解思路 整体结构 实现过程 入队列 插入数据时&#xff0c;插入到ist。…

尚品汇-(四)

&#xff08;1&#xff09;商品的基本知识 1.1基本信息—分类 一般情况可以分为两级或者三级。咱们的项目一共分为三级&#xff0c;即一级分类、二级分类、三级分类。 比如&#xff1a;家用电器是一级分类&#xff0c;电视是二级分类&#xff0c;那么超薄电视就是三级分类。…

《计算机英语》 Unit 5 Networking 网络

Section A Networking 网络 The need to share information and resources among different computers has led to linked computer systems, called networks, in which computers are connected so that data can be transferred from machine to machine. 不同计算机之间共享…