热门标签 | HotTags
当前位置:  开发笔记 > 程序员 > 正文

【洛谷】P1541乌龟棋(四维背包dp)

题目背景小明过生日的时候,爸爸送给他一副乌龟棋当作礼物。题目描述乌龟棋的棋盘是一行N个格子,每个格子上一个分数(非负整数)。棋盘第1格是唯一的起点,第N格是终点,游戏要求玩家控制一个乌龟棋子从起点出发

题目背景

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

题目描述

乌龟棋的棋盘是一行N个格子,每个格子上一个分数(非负整数)。棋盘第1格是唯一的起点,第N格是终点,游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

乌龟棋中M张爬行卡片,分成4种不同的类型(M张卡片中不一定包含所有4种类型的卡片,见样例),每种类型的卡片上分别标有1、2、3、4四个数字之一,表示使用这种卡片后,乌龟棋子将向前爬行相应的格子数。游戏中,玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片,控制乌龟棋子前进相应的格子数,每张卡片只能使用一次。

游戏中,乌龟棋子自动获得起点格子的分数,并且在后续的爬行中每到达一个格子,就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。

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

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

输入输出格式

输入格式:

 

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

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

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

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

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

 

输出格式:

 

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

 

输入输出样例

输入样例#1:
9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1
输出样例#1:
73

说明

每个测试点1s

小明使用爬行卡片顺序为1,1,3,1,2,得到的分数为6+10+14+8+18+17=73。注意,由于起点是1,所以自动获得第1格的分数6。

对于30%的数据有1≤N≤30,1≤M≤12。

对于50%的数据有1≤N≤120,1≤M≤50,且4种爬行卡片,每种卡片的张数不会超过20。

对于100%的数据有1≤N≤350,1≤M≤120,且4种爬行卡片,每种卡片的张数不会超过40;0≤ai≤100,1≤i≤N;1≤bi≤4,1≤i≤M。

-------------------------------------------------------------------------------------------------

分析:我自带buff:眼瞎,没看到卡片上的数字只有1-4,死活不会(估计看到了也不会)。

  其实这是个背包dp   

 1 #include 
2 #include
3 using namespace std;
4 const int maxn=400,maxm=40;
5 int dp[40][40][40][40],a[maxn],cnt[5];
6 int main()
7 {
8 int n,m,x;
9 scanf("%d%d",&n,&m);
10 for(int i=1;i<=n;i++) scanf("%d",&a[i]);
11 for(int i=1;i<=m;i++)
12 {
13 scanf("%d",&x);
14 cnt[x]++;
15 }
16 for(int i=0;i<=cnt[1];i++)
17 for(int j=0;j<=cnt[2];j++)
18 for(int k=0;k<=cnt[3];k++)
19 for(int l=0;l<=cnt[4];l++)
20 {
21 dp[i][j][k][l]
22 =max(
23 max( dp[max(i-1,0)][j][k][l], dp[i][max(j-1,0)][k][l] ),
24 max( dp[i][j][max(k-1,0)][l], dp[i][j][k][max(l-1,0)] )
25 );
26 dp[i][j][k][l]+=a[1+i+2*j+3*k+4*l];
27 }
28 printf("%d",dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]]);
29 return 0;
30 }

解决【洛谷】P1541 乌龟棋,打卡

 


推荐阅读
  • 本文介绍了使用CentOS7.0 U盘刻录工具进行安装的详细步骤,包括使用USBWriter工具刻录ISO文件到USB驱动器、格式化USB磁盘、设置启动顺序等。通过本文的指导,用户可以轻松地使用U盘安装CentOS7.0操作系统。 ... [详细]
  • 在Docker中,将主机目录挂载到容器中作为volume使用时,常常会遇到文件权限问题。这是因为容器内外的UID不同所导致的。本文介绍了解决这个问题的方法,包括使用gosu和suexec工具以及在Dockerfile中配置volume的权限。通过这些方法,可以避免在使用Docker时出现无写权限的情况。 ... [详细]
  • 本文介绍了使用kotlin实现动画效果的方法,包括上下移动、放大缩小、旋转等功能。通过代码示例演示了如何使用ObjectAnimator和AnimatorSet来实现动画效果,并提供了实现抖动效果的代码。同时还介绍了如何使用translationY和translationX来实现上下和左右移动的效果。最后还提供了一个anim_small.xml文件的代码示例,可以用来实现放大缩小的效果。 ... [详细]
  • Spring源码解密之默认标签的解析方式分析
    本文分析了Spring源码解密中默认标签的解析方式。通过对命名空间的判断,区分默认命名空间和自定义命名空间,并采用不同的解析方式。其中,bean标签的解析最为复杂和重要。 ... [详细]
  • VScode格式化文档换行或不换行的设置方法
    本文介绍了在VScode中设置格式化文档换行或不换行的方法,包括使用插件和修改settings.json文件的内容。详细步骤为:找到settings.json文件,将其中的代码替换为指定的代码。 ... [详细]
  • Nginx使用(server参数配置)
    本文介绍了Nginx的使用,重点讲解了server参数配置,包括端口号、主机名、根目录等内容。同时,还介绍了Nginx的反向代理功能。 ... [详细]
  • 基于layUI的图片上传前预览功能的2种实现方式
    本文介绍了基于layUI的图片上传前预览功能的两种实现方式:一种是使用blob+FileReader,另一种是使用layUI自带的参数。通过选择文件后点击文件名,在页面中间弹窗内预览图片。其中,layUI自带的参数实现了图片预览功能。该功能依赖于layUI的上传模块,并使用了blob和FileReader来读取本地文件并获取图像的base64编码。点击文件名时会执行See()函数。摘要长度为169字。 ... [详细]
  • 搭建Windows Server 2012 R2 IIS8.5+PHP(FastCGI)+MySQL环境的详细步骤
    本文详细介绍了搭建Windows Server 2012 R2 IIS8.5+PHP(FastCGI)+MySQL环境的步骤,包括环境说明、相关软件下载的地址以及所需的插件下载地址。 ... [详细]
  • 如何去除Win7快捷方式的箭头
    本文介绍了如何去除Win7快捷方式的箭头的方法,通过生成一个透明的ico图标并将其命名为Empty.ico,将图标复制到windows目录下,并导入注册表,即可去除箭头。这样做可以改善默认快捷方式的外观,提升桌面整洁度。 ... [详细]
  • 向QTextEdit拖放文件的方法及实现步骤
    本文介绍了在使用QTextEdit时如何实现拖放文件的功能,包括相关的方法和实现步骤。通过重写dragEnterEvent和dropEvent函数,并结合QMimeData和QUrl等类,可以轻松实现向QTextEdit拖放文件的功能。详细的代码实现和说明可以参考本文提供的示例代码。 ... [详细]
  • 本文介绍了数据库的存储结构及其重要性,强调了关系数据库范例中将逻辑存储与物理存储分开的必要性。通过逻辑结构和物理结构的分离,可以实现对物理存储的重新组织和数据库的迁移,而应用程序不会察觉到任何更改。文章还展示了Oracle数据库的逻辑结构和物理结构,并介绍了表空间的概念和作用。 ... [详细]
  • 最近学习反射机制的时候Properties.load(读取本地文件流的时候怎么也找不到加载文件后面发现IDEA的默认根目录是在它的Project工程下IDEA的文件目录和Ec ... [详细]
  • Linux重启网络命令实例及关机和重启示例教程
    本文介绍了Linux系统中重启网络命令的实例,以及使用不同方式关机和重启系统的示例教程。包括使用图形界面和控制台访问系统的方法,以及使用shutdown命令进行系统关机和重启的句法和用法。 ... [详细]
  • windows便签快捷键_用了windows十几年,没想到竟然这么好用!隐藏的功能你知道吗?
    本文介绍了使用windows操作系统时的一些隐藏功能,包括便签快捷键、截图功能等。同时探讨了windows和macOS操作系统之间的优劣比较,以及人们对于这两个系统的不同看法。 ... [详细]
  • Webpack5内置处理图片资源的配置方法
    本文介绍了在Webpack5中处理图片资源的配置方法。在Webpack4中,我们需要使用file-loader和url-loader来处理图片资源,但是在Webpack5中,这两个Loader的功能已经被内置到Webpack中,我们只需要简单配置即可实现图片资源的处理。本文还介绍了一些常用的配置方法,如匹配不同类型的图片文件、设置输出路径等。通过本文的学习,读者可以快速掌握Webpack5处理图片资源的方法。 ... [详细]
author-avatar
熊字饼爱优乐美
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有