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

AcWing---乌龟棋---线性dp

312. 乌龟棋 - AcWing题库 

思路:

原来没有碰到过类似的题:

  1. dp数组为思维:dp[i][j][k][r],分别表示用了i个第一类型卡片,j个第二类型卡片...所到的格子数的最大分数,为啥不用记录乌龟到了哪里呢?因为i*1+j*2+k*3+r*4已经表明了小乌龟的终点位置了。
  2. 状态转移方程式dp[i][j][k][r]=max(dp[i-1][j][k][r],dp[i][j-1][k][r],...)+a[i*1+j*2+k*3+r*4]
  3. 数组初始化:dp[0][1][2][3]=0

C++代码:

#include<bits/stdc++.h>
using namespace std;int g[41][41][41][41];
int n,m;
int a[400];
int b[5];int main(){cin>>n>>m;for(int i=0;i<n;i++){cin>>a[i];}for(int i=0;i<m;i++){int temp;cin>>temp;b[temp]++;}g[0][0][0][0]=a[0];for(int i=0;i<=b[1];i++){for(int j=0;j<=b[2];j++){for(int k=0;k<=b[3];k++){for(int r=0;r<=b[4];r++){if(i-1>=0){g[i][j][k][r]=max(g[i][j][k][r],g[i-1][j][k][r]+a[i+2*j+3*k+4*r]);}if(j-1>=0){g[i][j][k][r]=max(g[i][j][k][r],g[i][j-1][k][r]+a[i+2*j+3*k+4*r]);}if(k-1>=0){g[i][j][k][r]=max(g[i][j][k][r],g[i][j][k-1][r]+a[i+2*j+3*k+4*r]);}if(r-1>=0){g[i][j][k][r]=max(g[i][j][k][r],g[i][j][k][r-1]+a[i+2*j+3*k+4*r]);}}}}}cout<<g[b[1]][b[2]][b[3]][b[4]];return 0;
}

 python代码:

n,m=map(int,input().split())
a=list(map(int,input().split()))
b_temp=list(map(int,input().split()))
b=[0]*5
for i in b_temp:b[i]+=1g=[[[[0 for _ in range(41)] for _ in range(41)] for _ in range(41)] for _ in range(41)]
g[0][0][0][0]=a[0]
for i in range(b[1]+1):for j in range(b[2]+1):for k in range(b[3]+1):for r in range(b[4]+1):if i-1>=0:g[i][j][k][r]=max(g[i][j][k][r],g[i-1][j][k][r]+a[i+j*2+k*3+r*4]);if j-1>=0:g[i][j][k][r]=max(g[i][j][k][r],g[i][j-1][k][r]+a[i+j*2+k*3+r*4]);if k-1>=0:g[i][j][k][r]=max(g[i][j][k][r],g[i][j][k-1][r]+a[i+j*2+k*3+r*4]);if r-1>=0:g[i][j][k][r]=max(g[i][j][k][r],g[i][j][k][r-1]+a[i+j*2+k*3+r*4]);
print(g[b[1]][b[2]][b[3]][b[4]])

相关文章:

AcWing---乌龟棋---线性dp

312. 乌龟棋 - AcWing题库 思路&#xff1a; 原来没有碰到过类似的题&#xff1a; dp数组为思维&#xff1a;dp[i][j][k][r]&#xff0c;分别表示用了i个第一类型卡片&#xff0c;j个第二类型卡片...所到的格子数的最大分数&#xff0c;为啥不用记录乌龟到了哪里呢&#xff1…...

python代码使用过程中使用快捷键注释时报错

1.代码 2.代码报错 3.代码注释后的结果 4. 原因...

go之web框架gin

介绍 Gin 是一个用 Go (Golang) 编写的 Web 框架。 它具有类似 martini 的 API&#xff0c;性能要好得多&#xff0c;多亏了 httprouter&#xff0c;速度提高了 40 倍。 如果您需要性能和良好的生产力&#xff0c;您一定会喜欢 Gin。 安装 go get -u github.com/gin-gonic/g…...

SpringBoot 定时任务实践、定时任务按指定时间执行

Q1. springboot怎样创建定时任务&#xff1f; 很显然&#xff0c;人人都知道&#xff0c;Scheduled(cron ".....") Q2. 如上所示创建了定时任务却未能执行是为什么&#xff1f; 如果你的cron确定没写错的话 cron表达式是否合法&#xff0c;可参考此处&#xff0c…...

MYSQL数据库故障排除与优化

目录 MySQL 单实例故障排查 MySQL 主从故障排查 MySQL 优化 MySQL 单实例故障排查 故障现象 1 ERROR 2002 (HY000): Cant connect to local MySQL server through socket /data/mysql/mysql.sock (2) 问题分析&#xff1a;以上这种情况一般都…...

算法-数论-蓝桥杯

算法-数论 1、最大公约数 def gcd(a,b):if b 0:return areturn gcd(b, a%b) # a和b的最大公约数等于b与a mod b 的最大公约数def gcd(a,b):while b ! 0:cur aa bb cur%bpassreturn a欧几里得算法 a可以表示成a kb r&#xff08;a&#xff0c;b&#xff0c;k&#xff0c…...

222.完全二叉树节点个数

给你一棵 完全二叉树 的根节点 root &#xff0c;求出该树的节点个数。 完全二叉树 的定义如下&#xff1a;在完全二叉树中&#xff0c;除了最底层节点可能没填满外&#xff0c;其余每层节点数都达到最大值&#xff0c;并且最下面一层的节点都集中在该层最左边的若干位置。若最…...

C++中的string类操作详解

引言 针对C中的string&#xff0c;本文主要讲解如何对其进行插入、删除、查找、比较、截断、分割以及与数字之间的相互转换等。 字符串插入 1. append方法 std::string str "hello"; str.append(7, w); // 在末尾添加7个字符w str.append("wwwwwww");…...

Java绘图坐标体系

一、介绍 下图说明了Java坐标系。坐标原点位于左上角&#xff0c;以像素为单位。在Java坐标系中&#xff0c;第一个是x坐标&#xff0c;表示当前位置为水平方向&#xff0c;距离坐标原点x个像素&#xff1b;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐…...

【MATLAB源码-第38期】基于OFDM的块状导频和梳状导频误码率性能对比,以及LS/LMMSE两种信道估计方法以及不同调制方式对比。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 块状导频和梳状导频都是用于无线通信系统中信道估计的方法。 块状导频&#xff1a; 定义&#xff1a; 在频域上&#xff0c;块状导频是连续放置的一组导频符号。这意味着所有的导频符号都集中在一个短的时间段内发送。 优点…...

javaWeb车辆管理系统设计与实现

摘 要 随着经济的日益增长,车辆作为最重要的交通工具,在企事业单位中得以普及,单位的车辆数目已经远远不止简单的几辆,与此同时就产生了车辆资源的合理分配使用问题。 企业车辆管理系统运用现代化的计算机管理手段&#xff0c;不但可以对车辆的使用进行合理的管理&#xff0c;…...

【DM8】间隔分区

是范围分区的一个扩展 如果使用了间隔函数做分区&#xff0c;在数据插入的时候&#xff0c;如果没有合适的分区&#xff0c;数据库会自动创建一个新的分区。 –year往后推两年 SELECT SYSDATE numtoyminterval(2,‘YEAR’); –month往后推两年 SELECT SYSDATE numtoyminterv…...

0基础如何进入IT行业?

目录 0基础如何进入IT行业&#xff1f; 一、学习路径 二、技能培养 三、实践经验 0基础如何进入IT行业&#xff1f; 对于没有任何相关背景知识的人来说&#xff0c;成功进入IT行业可能看起来是一个遥不可及的目标。然而&#xff0c;只要有正确的方法和坚持不懈的努力&#…...

C#将Console写至文件,且文件固定最大长度

参考文章 将C#的Console.Write同步到控制台和log文件输出 业务需求 在生产环境中&#xff0c;控制台窗口不便展示出来。 为了在生产环境中&#xff0c;完整记录控制台应用的输出&#xff0c;选择将其输出到文件中。 但是&#xff0c;一次性存储所有输出的话&#xff0c;文件会…...

《CSS 知识点》仅在文本有省略号时添加 tip 信息

html <div ref"btns" class"btns"><div class"btn" >这是一段很短的文本.</div><div class"btn" >这是一段很短的文本.</div><div class"btn" >这是一段很长的文本.有省略号和tip.<…...

彩虹聚合DNS管理系统v1.0全新发布

聚合DNS管理系统&#xff08;https://github.com/netcccyun/dnsmgr&#xff09;可以实现在一个网站内管理多个平台的域名解析&#xff0c;目前已支持的域名平台有&#xff1a;阿里云、腾讯云、华为云、西部数码、CloudFlare。本系统支持多用户&#xff0c;每个用户可分配不同的…...

3.10 Python数据类型转换

Python类型转换&#xff0c;Python数据类型转换函数大全 虽然 Python 是弱类型编程语言&#xff0c;不需要像Java或 C 语言那样还要在使用变量前声明变量的类型&#xff0c;但在一些特定场景中&#xff0c;仍然需要用到类型转换。 比如说&#xff0c;我们想通过使用 print() …...

Kotlin基础学习

Kotlin基础学习主要涵盖安装Kotlin编译器、了解基础语法、学习变量声明、类型推断、函数定义以及控制结构等方面。以下是一个简要的Kotlin基础学习指南&#xff1a; 一、安装Kotlin 首先&#xff0c;你需要从JetBrains的官方网站下载并安装Kotlin编译器。同时&#xff0c;你也…...

配置交换机 SSH 管理和端口安全——实验1:配置交换机基本安全和 SSH管理

实验目的 通过本实验可以掌握&#xff1a; 交换机基本安全配置。SSH 的工作原理和 SSH服务端和客户端的配置。 实验拓扑 交换机基本安全和 SSH管理实验拓扑如图所示。 交换机基本安全和 SSH管理实验拓扑 实验步骤 &#xff08;1&#xff09;配置交换机S1 Switch>enab…...

海山数据库(He3DB)原理剖析:浅析Doris跨源分析能力

Doris湖仓分析背景&#xff1a; Doris多数据源功能演进 Doris的生态近年来围绕湖仓分析做了较多工作&#xff0c;Doris一直在积极拓宽大数据生态的OLAP分析市场&#xff0c;Doris2.0之后为了满足湖仓分析场景&#xff0c;围绕multi-catalog、数据缓存、容错、pipeline资源管理…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...

【Linux】Linux安装并配置RabbitMQ

目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的&#xff0c;需要先安…...