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

备战蓝桥杯---动态规划(基础1)

先看几道比较简单的题:

直接f[i][j]=f[i-1][j]+f[i][j-1]即可(注意有马的地方赋值为0)

下面是递推循环方式实现的AC代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[30][30];
int n,m,x,y;
signed main(){cin>>n>>m>>x>>y;x++;y++;m++;n++;a[1][1]=1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if((abs(x-i)==1&&abs(y-j)==2)||(abs(x-i)==2&&abs(y-j)==1)||(x==i&&y==j)){a[i][j]=0;continue;}if(i==1&&j==1) continue;a[i][j]=a[i][j-1]+a[i-1][j];}}cout<<a[n][m];
}

下面是记忆化数组实现的AC代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[30][30];
int n,m,x,y;
int dir[8][2]={{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}};
int dp(int x,int y){if(x<=0||x>n||y>m||y<=0) return 0;if(a[x][y]!=-1) return a[x][y];return a[x][y]=dp(x-1,y)+dp(x,y-1);
}
signed main(){cin>>n>>m>>x>>y;x++;y++;n++;m++;memset(a,-1,sizeof(a));a[1][1]=1;a[x][y]=0;for(int i=0;i<8;i++){int xx=x+dir[i][0];int yy=y+dir[i][1];if(xx<=0||xx>n||yy>m||yy<=0) continue;a[xx][yy]=0;}cout<<dp(n,m);
}

接题:

我们定义f[i][j]为第j同学的方案数(注意n位同学旁边为1号与n-1)

下面是递推循环方式实现的AC代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int dp[40][40];
signed main(){cin>>n>>m;dp[1][0]=1;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(j==1){dp[j][i]=dp[n][i-1]+dp[j+1][i-1];}else if(j==n){dp[j][i]=dp[j-1][i-1]+dp[1][i-1];}else{dp[j][i]=dp[j-1][i-1]+dp[j+1][i-1];}}}cout<<dp[1][m];
}

下面是用记忆化搜索的实现代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int dp[40][40];
int f(int x,int y){if(y<0) return 0;if(dp[x][y]!=-1) return dp[x][y];if(x==1) return dp[x][y]=f(n,y-1)+f(x+1,y-1);if(x==n) return dp[x][y]=f(x-1,y-1)+f(1,y-1);return dp[x][y]=f(x-1,y-1)+f(x+1,y-1);
}
signed main(){cin>>n>>m;memset(dp,-1,sizeof(dp));dp[1][0]=1;for(int i=2;i<=n;i++) dp[i][0]=0;cout<<f(1,m);
}

注意,在用记忆化搜索时,memset语句是必要的,如果不加,那么dp[x][y]!=0时返回,但事实上,我们有很多地方值为0,意味这退出情况大多是y<0在起作用,因此,记忆化的作用发挥不出来,虽然答案对,但是运行很慢。

相关文章:

备战蓝桥杯---动态规划(基础1)

先看几道比较简单的题&#xff1a; 直接f[i][j]f[i-1][j]f[i][j-1]即可&#xff08;注意有马的地方赋值为0&#xff09; 下面是递推循环方式实现的AC代码&#xff1a; #include<bits/stdc.h> using namespace std; #define int long long int a[30][30]; int n,m,x,y; …...

CVE-2018-19518 漏洞复现

CVE-2018-19518 漏洞介绍 IMAP协议&#xff08;因特网消息访问协议&#xff09;它的主要作用是邮件客户端可以通过这种协议从邮件服务器上获取邮件的信息&#xff0c;下载邮件等。它运行在TCP/IP协议之上&#xff0c;使用的端口是143。在php中调用的是imap_open函数。 PHP 的…...

Python爬虫实战:抓取猫眼电影排行榜top100#4

爬虫专栏系列&#xff1a;http://t.csdnimg.cn/Oiun0 抓取猫眼电影排行 本节中&#xff0c;我们利用 requests 库和正则表达式来抓取猫眼电影 TOP100 的相关内容。requests 比 urllib 使用更加方便&#xff0c;而且目前我们还没有系统学习 HTML 解析库&#xff0c;所以这里就…...

Fiddler抓包工具之fiddler界面工具栏介绍

Fiddler界面工具栏介绍 &#xff08;1&#xff09;WinConfig&#xff1a;windows 使用了一种叫做“AppContainer”的隔离技术&#xff0c;使得一些流量无法正常捕获&#xff0c;在 fiddler中点击 WinConfig 按钮可以解除这个诅咒&#xff0c;这个与菜单栏 Tools→Win8 Loopback…...

LabVIEW工业监控系统

LabVIEW工业监控系统 介绍了一个基于LabVIEW软件开发的工业监控系统。系统通过虚拟测控技术和先进的数据处理能力&#xff0c;实现对工业过程的高效监控&#xff0c;提升系统的自动化和智能化水平&#xff0c;从而满足现代工业对高效率、高稳定性和低成本的需求。 随着工业自…...

Linux 文件连接:符号链接与硬链接

Linux 文件连接&#xff1a;符号链接与硬链接 介绍 在 Linux 系统中&#xff0c;文件连接是一个强大的概念&#xff0c;它允许我们在文件系统中创建引用&#xff0c;从而使得文件和目录之间产生联系。在本文中&#xff0c;我们将深入探讨两种主要类型的文件连接&#xff1a;符…...

数据分类分级

一段时间没写文章了&#xff0c;最近做政府数据治理方面的项目&#xff0c;数据治理一个重要的内容是数据安全&#xff0c;会涉及数据的分类分级&#xff0c;是数据治理的基础。 随着“十四五”规划推行&#xff0c;数据要素概念与意识全面铺开&#xff0c;国家、政府机构、企业…...

第三十天| 51. N皇后

Leetcode 51. N皇后 题目链接&#xff1a;51 N皇后 题干&#xff1a;按照国际象棋的规则&#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上&#xff0c;并且使皇后彼此之间不能相互攻击。 给你一个整…...

pythn-scipy 查漏补缺

1. 2. 3. 4. 5. 6. 7. 8. 9. 偏度 skewness&#xff0c;峰度 kurtosis...

【JavaScript 漫游】【013】Date 对象知识点摘录

文章简介 本文为【JavaScript 漫游】专栏的第 013 篇文章&#xff0c;记录了 JS 语言中 Date 对象的重要知识点。 普通函数的用法构造函数的用法日期的运算静态方法&#xff0c;包括&#xff1a;Date.now()、Date.parse() 和 Date.UTC()实例方法&#xff0c;包括&#xff1a;…...

vue.config.js和webpack.config.js区别

webpack.config.js和vue.config.js的区别 webpack.config.js是webpack的配置文件&#xff0c;所有使用webpack作为打包工具的项目都可以使用&#xff0c;vue的项目可以使用&#xff0c;react的项目也可以使用。 vue.config.js是vue项目的配置文件&#xff0c;专用于vue项目。…...

H12-821_73

73.某台路由器Router LSA如图所示&#xff0c;下列说法中错误的是&#xff1f; A.本路由器的Router ID为10.0.12.1 B.本路由器为DR C.本路由器已建立邻接关系 D.本路由器支持外部路由引入 答案&#xff1a;B 注释&#xff1a; LSA中的链路信息Link ID&#xff0c;Data&#xf…...

postman执行批量测试

1.背景 有许多的人常常需要使用第三方系统进行重复的数据查询&#xff0c;本文介绍使用PostMan的方式对数据进行批量的查询&#xff0c;减少重复的劳动。 2.工具下载 3.初入门 一、如图示进行点击&#xff0c;创建collection 二、输入对应的名称 三、创建Request并进行查…...

蓝桥杯基础知识8 list

蓝桥杯基础知识8 list 01 list 的定义和结构 lits使用频率较低&#xff0c;是一种双向链表容器&#xff0c;是标准模板库&#xff08;STL&#xff09;提供的一种序列容器&#xff0c;lsit容器以节点&#xff08;node&#xff09;的形式存储元素&#xff0c;使用指针将这些节点链…...

【DDD】学习笔记-理解领域模型

Eric Evans 的领域驱动设计是对软件设计领域的一次重新审视&#xff0c;是在面向对象语言大行其道时对数据建模的“拨乱反正”。Eric 强调了模型的重要性&#xff0c;例如他在书中总结了模型在领域驱动设计中的作用包括&#xff1a; 模型和设计的核心互相影响模型是团队所有成…...

v-if 和v-show 的区别

第074个 查看专栏目录: VUE ------ element UI 专栏目标 在vue和element UI联合技术栈的操控下&#xff0c;本专栏提供行之有效的源代码示例和信息点介绍&#xff0c;做到灵活运用。 提供vue2的一些基本操作&#xff1a;安装、引用&#xff0c;模板使用&#xff0c;computed&a…...

LabVIEW网络测控系统

LabVIEW网络测控系统 介绍了基于LabVIEW的网络测控系统的开发与应用&#xff0c;通过网络技术实现了远程的数据采集、监控和控制。系统采用LabVIEW软件与网络通信技术相结合&#xff0c;提高了系统的灵活性和扩展性&#xff0c;适用于各种工业和科研领域的远程测控需求。 随着…...

攻防世界 CTF Web方向 引导模式-难度1 —— 11-20题 wp精讲

PHP2 题目描述: 暂无 根据dirsearch的结果&#xff0c;只有index.php存在&#xff0c;里面也什么都没有 index.phps存在源码泄露&#xff0c;访问index.phps 由获取的代码可知&#xff0c;需要url解码(urldecode )后验证id为admin则通过 网页工具不能直接对字母进行url编码 …...

华为Eth-Trunk级联堆叠接入IPTV网络部署案例

Eth-Trunk级联堆叠接入IPTV网络部署案例 组网图形 图2 Eth-Trunk级联堆叠IPTV基本组网图 方案简介配置注意事项组网需求数据规划配置思路操作步骤配置文件 方案简介 随着IPTV业务的迅速发展&#xff0c;IPTV平台承载的用户也越来越多&#xff0c;用户对IPTV直播业务的可靠性…...

idea: 无法创建Java Class文件(SpringBoot)已解决

第一&#xff1a;点击file-->project Sructure... 第二步&#xff1a;点击Moudules 选择自己需要创建java的文件夹&#xff08;我这里选择的是main&#xff09;右键点击Sources&#xff0c;然后点击OK即可 然后就可以创建java类了...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

规则与人性的天平——由高考迟到事件引发的思考

当那位身着校服的考生在考场关闭1分钟后狂奔而至&#xff0c;他涨红的脸上写满绝望。铁门内秒针划过的弧度&#xff0c;成为改变人生的残酷抛物线。家长声嘶力竭的哀求与考务人员机械的"这是规定"&#xff0c;构成当代中国教育最尖锐的隐喻。 一、刚性规则的必要性 …...

前端工具库lodash与lodash-es区别详解

lodash 和 lodash-es 是同一工具库的两个不同版本&#xff0c;核心功能完全一致&#xff0c;主要区别在于模块化格式和优化方式&#xff0c;适合不同的开发环境。以下是详细对比&#xff1a; 1. 模块化格式 lodash 使用 CommonJS 模块格式&#xff08;require/module.exports&a…...

【版本控制】GitHub Desktop 入门教程与开源协作全流程解析

目录 0 引言1 GitHub Desktop 入门教程1.1 安装与基础配置1.2 核心功能使用指南仓库管理日常开发流程分支管理 2 GitHub 开源协作流程详解2.1 Fork & Pull Request 模型2.2 完整协作流程步骤步骤 1: Fork&#xff08;创建个人副本&#xff09;步骤 2: Clone&#xff08;克隆…...

深入浅出JavaScript中的ArrayBuffer:二进制数据的“瑞士军刀”

深入浅出JavaScript中的ArrayBuffer&#xff1a;二进制数据的“瑞士军刀” 在JavaScript中&#xff0c;我们经常需要处理文本、数组、对象等数据类型。但当我们需要处理文件上传、图像处理、网络通信等场景时&#xff0c;单纯依赖字符串或数组就显得力不从心了。这时&#xff…...

JUC并发编程(二)Monitor/自旋/轻量级/锁膨胀/wait/notify/锁消除

目录 一 基础 1 概念 2 卖票问题 3 转账问题 二 锁机制与优化策略 0 Monitor 1 轻量级锁 2 锁膨胀 3 自旋 4 偏向锁 5 锁消除 6 wait /notify 7 sleep与wait的对比 8 join原理 一 基础 1 概念 临界区 一段代码块内如果存在对共享资源的多线程读写操作&#xf…...