动态规划刷题(算法竞赛、蓝桥杯)--乌龟棋(线性DP)

1、题目链接:[NOIP2010 提高组] 乌龟棋 - 洛谷

75c8d88d34054a059a7278ea202becfb.png

84c5a7e8904446729c0f69e68e75483f.png

#include <bits/stdc++.h> 
using namespace std;
const int M=41;
int f[M][M][M][M],num[351],g[5],n,m,x;
//f[a][b][c][d]表示放a个1b个2c个3d个4的总得分 
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&num[i]);
	}
	f[0][0][0][0]=num[1];
	for(int i=1;i<=m;i++){
		scanf("%d",&x);
		g[x]++;
	}
	for(int a=0;a<=g[1];a++){
		for(int b=0;b<=g[2];b++){
			for(int c=0;c<=g[3];c++){
				for(int d=0;d<=g[4];d++){
					int r=1+a+b*2+c*3+4*d;//起点得分加上用了对应卡数的得分
					//比较不放与放的总得分
					// 放了要加上放后达到格子对应的分数 
					if(a!=0)f[a][b][c][d]=max(f[a][b][c][d],f[a-1][b][c][d]+num[r]);
					if(b!=0)f[a][b][c][d]=max(f[a][b][c][d],f[a][b-1][c][d]+num[r]);
					if(c!=0)f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c-1][d]+num[r]);
					if(d!=0)f[a][b][c][d]=max(f[a][b][c][d],f[a][b][c][d-1]+num[r]);
				}
			}
		}
	}
	printf("%d",f[g[1]][g[2]][g[3]][g[4]]);//枚举完所有的情况 
	return 0;
}

 

 

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

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

相关文章

创新指南|贝恩的产品经理RAPID框架:解决问题的分步指南,使决策过程既高效又民主

您是否曾发现自己陷入项目的阵痛之中&#xff0c;决策混乱、角色不明确、团队成员之间的冲突不断升级&#xff1f;作为产品经理&#xff0c;驾驭这艘船穿过如此汹涌的水域可能是令人畏惧的。应对这些挑战的关键在于采用清晰、结构化的决策方法。输入贝恩的 RAPID 框架&#xff…

软件测试用例(2)

具体的设计方法 -- 黑盒测试 因果图 因果图是一种简化的逻辑图, 能直观地表明程序的输入条件(原因)和输出动作(结果)之间的相互关系. 因果图法是借助图形来设计测试用例的一种系统方法, 特别适用于被测试程序具有多种输入条件, 程序的输出又依赖于输入条件的各种情况. 因果图…

Linux-进程概念

1. 进程基本概念 书面概念&#xff1a;程序的一个执行实例&#xff0c;正在执行的程序等 内核概念&#xff1a;担当分配系统资源&#xff08;CPU时间&#xff0c;内存&#xff09;的实体。 2. 描述和组织进程-PCB PCB&#xff08;process contral block&#xff09;&#xff0…

【讲解下如何Stable Diffusion本地部署】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…

20240324-2-频繁模式FrequentPattern

频繁模式(frequent pattern) 频繁模式一般是指频繁地出现在数据集中的模式。这种频繁模式和关联规则是数据挖掘中想要挖掘的知识。我们都知道一个很有趣的故事&#xff0c;就是啤酒和尿布的故事&#xff0c; 在某些特定的情况下&#xff0c;“啤酒”与“尿布”两件看上去毫无关…

SCP 从Linux快速下载文件到Windows本地

需求&#xff1a;通过mobaxterm将大文件拖动到windows本地速度太慢。 环境&#xff1a;本地是Windows&#xff0c;安装了Git。 操作&#xff1a;进入文件夹内&#xff0c;鼠标右键&#xff0c;点击Git Bash here&#xff0c;然后输入命令即可。这样的话&#xff0c;其实自己本…

java农家乐旅游管理系统springboot+vue

实现了一个完整的农家乐系统&#xff0c;其中主要有用户表模块、关于我们模块、收藏表模块、公告信息模块、酒店预订模块、酒店信息模块、景区信息模块、景区订票模块、景点分类模块、会员等级模块、会员模块、交流论坛模块、度假村信息模块、配置文件模块、在线客服模块、关于…

基于深度学习的番茄成熟度检测系统(网页版+YOLOv8/v7/v6/v5代码+训练数据集)

摘要&#xff1a;在本博客中&#xff0c;我们深入探讨了基于YOLOv8/v7/v6/v5的番茄成熟度检测系统。核心技术基于YOLOv8&#xff0c;同时融合了YOLOv7、YOLOv6、YOLOv5的算法&#xff0c;对比了它们在性能指标上的差异。本文详细介绍了国内外在此领域的研究现状、数据集的处理方…

9.图像中值腐蚀膨胀滤波的实现

1 简介 在第七章介绍了基于三种卷积前的图像填充方式&#xff0c;并生成了3X3的图像卷积模板&#xff0c;第八章运用这种卷积模板进行了均值滤波的FPGA实现与MATLAB实现&#xff0c;验证了卷积模板生成的正确性和均值滤波算法的MATLAB算法实现。   由于均值滤波、中值滤波、腐…

Flask Python:如何获取不同请求方式的参数

目录 前言 1. 获取GET请求中的查询参数 2. 获取POST请求中的表单数据 3. 获取JSON数据 总结 前言 在使用Flask开发Web应用时&#xff0c;我们经常需要获取不同请求方式的参数。Flask提供了多种方式来获取不同请求方式的参数&#xff0c;包括GET请求中的查询参数、POST请求…

Spring Boot Mockito (二)

Spring Boot Mockito (二) 基于第一篇Spring Boot Mockito (一) 这篇文章主要是讲解Spring boot 与 Mockito 集成持久层接口层单元测试。 1. 引入数据库 h2及其依赖包 <dependency><groupId>com.h2database</groupId><artifactId>h2</artifactId…

JavaScript基础代码练习之冒泡排序

一、要求对一个数组进行冒泡排序&#xff0c;并将排序后的结果输出到控制台。在代码中&#xff0c;数组 arr 包含了一组数字&#xff0c;然后使用嵌套的循环来进行冒泡排序。 二、编写代码 <!DOCTYPE html> <html lang"en"><head><meta chars…

NOI - OpenJudge - 2.5基本算法之搜索 - 1490:A Knight‘s Journey - 超详解析(含AC代码)

点赞关注吧~ 1490:A Knights Journey 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述 Background The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey around the world. When…

《QT实用小工具·九》设备按钮控件

1、概述 源码放在文章末尾 该项目实现了设备按钮控件&#xff0c;主要包含如下功能&#xff1a; 可设置按钮样式 圆形、警察、气泡、气泡2、消息、消息2。可设置按钮颜色 布防、撤防、报警、旁路、故障。可设置报警切换及对应报警切换的颜色。可设置显示的防区号。可设置是否…

实验报告答案

基本任务&#xff08;必做&#xff09; 先用普通用户&#xff08;自己的姓名拼音&#xff09;登录再操作 编程有代码截图和执行过程结果截图 代写获取&#xff1a; https://laowangall.oss-cn-beijing.aliyuncs.com/studentall.pdf 1. Linux的Shell编程 &#xff08;1&am…

实操:Dropzone.js实现文件上传

&#x1f3e0;官网 点我前往 &#x1f953;依赖 <script src"https://unpkg.com/dropzone5/dist/min/dropzone.min.js"></script> <link rel"stylesheet" href"https://unpkg.com/dropzone5/dist/min/dropzone.min.css" type&…

unity工程输出的log在哪里?

在编辑器里进行活动输出的log位置&#xff1a; C:\Users\username\AppData\Local\Unity\Editor\Editor.log ------------------------------------ 已经打包完成&#xff0c;形成的exe运行后的log位置&#xff1a; C:\Users\xxx用户\AppData\LocalLow\xx公司\xx项目

【Qt】事件

目录 一、介绍 二、进入离开事件 三、鼠标事件 3.1 鼠标单击事件 3.2 鼠标释放事件 3.3 鼠标双击事件 3.4 鼠标移动事件 3.5 滚轮事件 四、按键事件 4.1 单个按键 4.2 组合按键 五、定时器 5.1 QTimerEvent类 5.2 QTimer类 5.3 获取系统日期及时间 六、事件分…

【游戏逆向】逆向基础----CE使用和基础

windows逆向中&#xff0c;CE扮演着不可或缺的角色。 其根本原因是&#xff0c;上手简单,功能强大&#xff0c;提供多方位的突破口。 点击小电脑图标&#xff0c; 选择我们想要调试的程序&#xff0c; 就可以附加调试了。 很多的游戏保护驱动以及反调试手段&#xff0c;都针对…

澳门媒体发稿套餐9个增长技巧解析-华媒舍

澳门作为一个国际知名的旅游胜地&#xff0c;拥有丰富的媒体资源。利用澳门媒体发稿&#xff0c;既可以提升品牌知名度&#xff0c;又可以吸引更多的目标受众。下面是9个利用澳门媒体发稿套餐的增长技巧&#xff0c;帮助你充分发挥媒体的作用&#xff0c;实现品牌的增长。 1. 制…