备战蓝桥杯---动态规划(基础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)
先看几道比较简单的题: 直接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; …...

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

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

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

LabVIEW工业监控系统
LabVIEW工业监控系统 介绍了一个基于LabVIEW软件开发的工业监控系统。系统通过虚拟测控技术和先进的数据处理能力,实现对工业过程的高效监控,提升系统的自动化和智能化水平,从而满足现代工业对高效率、高稳定性和低成本的需求。 随着工业自…...
Linux 文件连接:符号链接与硬链接
Linux 文件连接:符号链接与硬链接 介绍 在 Linux 系统中,文件连接是一个强大的概念,它允许我们在文件系统中创建引用,从而使得文件和目录之间产生联系。在本文中,我们将深入探讨两种主要类型的文件连接:符…...
数据分类分级
一段时间没写文章了,最近做政府数据治理方面的项目,数据治理一个重要的内容是数据安全,会涉及数据的分类分级,是数据治理的基础。 随着“十四五”规划推行,数据要素概念与意识全面铺开,国家、政府机构、企业…...
第三十天| 51. N皇后
Leetcode 51. N皇后 题目链接:51 N皇后 题干:按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上,并且使皇后彼此之间不能相互攻击。 给你一个整…...

pythn-scipy 查漏补缺
1. 2. 3. 4. 5. 6. 7. 8. 9. 偏度 skewness,峰度 kurtosis...

【JavaScript 漫游】【013】Date 对象知识点摘录
文章简介 本文为【JavaScript 漫游】专栏的第 013 篇文章,记录了 JS 语言中 Date 对象的重要知识点。 普通函数的用法构造函数的用法日期的运算静态方法,包括:Date.now()、Date.parse() 和 Date.UTC()实例方法,包括:…...
vue.config.js和webpack.config.js区别
webpack.config.js和vue.config.js的区别 webpack.config.js是webpack的配置文件,所有使用webpack作为打包工具的项目都可以使用,vue的项目可以使用,react的项目也可以使用。 vue.config.js是vue项目的配置文件,专用于vue项目。…...

H12-821_73
73.某台路由器Router LSA如图所示,下列说法中错误的是? A.本路由器的Router ID为10.0.12.1 B.本路由器为DR C.本路由器已建立邻接关系 D.本路由器支持外部路由引入 答案:B 注释: LSA中的链路信息Link ID,Data…...

postman执行批量测试
1.背景 有许多的人常常需要使用第三方系统进行重复的数据查询,本文介绍使用PostMan的方式对数据进行批量的查询,减少重复的劳动。 2.工具下载 3.初入门 一、如图示进行点击,创建collection 二、输入对应的名称 三、创建Request并进行查…...
蓝桥杯基础知识8 list
蓝桥杯基础知识8 list 01 list 的定义和结构 lits使用频率较低,是一种双向链表容器,是标准模板库(STL)提供的一种序列容器,lsit容器以节点(node)的形式存储元素,使用指针将这些节点链…...

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

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

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

攻防世界 CTF Web方向 引导模式-难度1 —— 11-20题 wp精讲
PHP2 题目描述: 暂无 根据dirsearch的结果,只有index.php存在,里面也什么都没有 index.phps存在源码泄露,访问index.phps 由获取的代码可知,需要url解码(urldecode )后验证id为admin则通过 网页工具不能直接对字母进行url编码 …...
华为Eth-Trunk级联堆叠接入IPTV网络部署案例
Eth-Trunk级联堆叠接入IPTV网络部署案例 组网图形 图2 Eth-Trunk级联堆叠IPTV基本组网图 方案简介配置注意事项组网需求数据规划配置思路操作步骤配置文件 方案简介 随着IPTV业务的迅速发展,IPTV平台承载的用户也越来越多,用户对IPTV直播业务的可靠性…...

idea: 无法创建Java Class文件(SpringBoot)已解决
第一:点击file-->project Sructure... 第二步:点击Moudules 选择自己需要创建java的文件夹(我这里选择的是main)右键点击Sources,然后点击OK即可 然后就可以创建java类了...

51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...

Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...
前端高频面试题2:浏览器/计算机网络
本专栏相关链接 前端高频面试题1:HTML/CSS 前端高频面试题2:浏览器/计算机网络 前端高频面试题3:JavaScript 1.什么是强缓存、协商缓存? 强缓存: 当浏览器请求资源时,首先检查本地缓存是否命中。如果命…...

基于开源AI智能名片链动2 + 1模式S2B2C商城小程序的沉浸式体验营销研究
摘要:在消费市场竞争日益激烈的当下,传统体验营销方式存在诸多局限。本文聚焦开源AI智能名片链动2 1模式S2B2C商城小程序,探讨其在沉浸式体验营销中的应用。通过对比传统品鉴、工厂参观等初级体验方式,分析沉浸式体验的优势与价值…...

欢乐熊大话蓝牙知识17:多连接 BLE 怎么设计服务不会乱?分层思维来救场!
多连接 BLE 怎么设计服务不会乱?分层思维来救场! 作者按: 你是不是也遇到过 BLE 多连接时,调试现场像网吧“掉线风暴”? 温度传感器连上了,心率带丢了;一边 OTA 更新,一边通知卡壳。…...