备战蓝桥杯---动态规划(基础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在起作用,因此,记忆化的作用发挥不出来,虽然答案对,但是运行很慢。

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

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

相关文章

Hive窗口函数详解

一、 窗口函数知识点 1.1 窗户函数的定义 窗口函数可以拆分为【窗口函数】。窗口函数官网指路&#xff1a; LanguageManual WindowingAndAnalytics - Apache Hive - Apache Software Foundationhttps://cwiki.apache.org/confluence/display/Hive/LanguageManual%20Windowing…

【Linux】make和Makefile

目录 make和Makefile make和Makefile 我们使用vim编辑器的时候&#xff0c;在一个文件里写完代码要进行编译&#xff0c;要自己输入编译的指令。有没有一种可以进行自动化编译的方法——makefile文件&#xff0c;它可以指定具体的编译操作&#xff0c;写好makefile文件&#x…

项目02《游戏-13-开发》Unity3D

基于 项目02《游戏-12-开发》Unity3D &#xff0c; 任务 &#xff1a;宠物系统 及 人物头像血条 首先在主面板MainPanel预制体中新建一个Panel&#xff0c; 命名为PlayerInfo 新建Image&#xff0c;作为头像 新建Slider&#xff0c;作为血条 对Panel组件添加一个水…

案例:CentOS8 在 MySQL8.0 实现半同步复制

异步复制 MySQL 默认的复制即是异步的&#xff0c;主库在执行完客户端提交的事务后会立即将结果返给给客户端&#xff0c;并不关心从库是否已经接收并处理&#xff0c;这样就会有一个问题&#xff0c;主节点如果 crash 掉了&#xff0c;此时主节点上已经提交的事务可能并没有传…

滑动窗口的最大值

题目 239. 滑动窗口最大值 - 力扣&#xff08;LeetCode&#xff09; 思路 使用一个队列充当不断滑动的窗口&#xff0c;每次滑动记录其中的最大值&#xff1a; 如何在 O(1) 时间计算最大值&#xff0c;只需要一个特殊的数据结构「单调队列」&#xff0c;push 方法依然在队尾添…

Swift 隐藏宝藏:“逆天改命”调整方法重载(function overloading)优先级

概览 在 Swift 语言中有很多隐藏“宝藏”悄悄深埋在不为人知的角落&#xff0c;静静等待着有缘秃头码农们的大力挖掘。 而在这里&#xff0c;我们将介绍 Swift 语言中一个非常有用的秘技&#xff1a;方法重载优先级判断以及如何改变它。 在本篇博文中&#xff0c;您将学到如下…

腾讯云4核8G服务器性能如何?支持多少用户访问?

腾讯云4核8G服务器支持多少人在线访问&#xff1f;支持25人同时访问。实际上程序效率不同支持人数在线人数不同&#xff0c;公网带宽也是影响4核8G服务器并发数的一大因素&#xff0c;假设公网带宽太小&#xff0c;流量直接卡在入口&#xff0c;4核8G配置的CPU内存也会造成计算…

移动光猫gs3101超级密码及改桥接模式教程

文章目录 超级管理员账号改桥接模式路由器连接光猫&#xff0c;PPPOE拨号即可&#xff01;附录&#xff1a;如果需要改桥接的话不知道拨号密码咋办打开光猫Telnet功能Telnet 登录 参考文章 移动光猫吉比特GS3101超级账号获取更改桥接 移动光猫gs3101超级密码及改桥接模式教程 …

奶茶点餐|奶茶店自助点餐系统|基于微信小程序的饮品点单系统的设计与实现(源码+数据库+文档)

奶茶店自助点餐系统目录 目录 基于微信小程序的饮品点单系统的设计与实现 一、前言 二、系统功能设计 三、系统实现 1、商品信息管理 2、商品评价管理 3、商品订单管理 4、用户管理 四、数据库设计 1、实体ER图 2、具体的表设计如下所示&#xff1a; 五、核心代码 …

QXlsx Qt操作excel(3)

QXlsx 是一个用于处理Excel文件的开源C库。它允许你在你的C应用程序中读取和写入Microsoft Excel文件&#xff08;.xlsx格式&#xff09;。该库支持多种操作&#xff0c;包括创建新的工作簿、读取和写入单元格数据、格式化单元格、以及其他与Excel文件相关的功能。 关于QXlsx的…

【机器学习】数据清洗之识别异常点

&#x1f388;个人主页&#xff1a;甜美的江 &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;机器学习 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共同学习、交流进步…

猫头虎分享已解决Bug | Go Error: cannot use str (type string) as type int in assignment

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …

webgis后端安卓系统部署攻略

目录 前言 一、将后端项目编译ARM64 二、安卓手机安装termux 1.更换为国内源 2.安装ssh远程访问 3.安装文件远程访问 三、安装postgis数据库 1.安装数据库 2.数据库配置 3.数据导入 四、后端项目部署 五、自启动设置 总结 前言 因为之前一直做的H5APP开发&#xf…

HiveSQL——用户行为路径分析

注&#xff1a;参考文档&#xff1a; SQL之用户行为路径分析--HQL面试题46【拼多多面试题】_路径分析 sql-CSDN博客文章浏览阅读2k次&#xff0c;点赞6次&#xff0c;收藏19次。目录0 问题描述1 数据分析2 小结0 问题描述已知用户行为表 tracking_log&#xff0c; 大概字段有&…

Java多态原理

参考 虚方法 JVM杂记&#xff1a;对多态实现原理、虚方法表、虚方法、静态解析、动态链接的一些思考_多态和方法表的关系-CSDN博客 静态分派与动态分派 &#xff08;JVM&#xff09;Java虚拟机&#xff1a;静态分派 & 动态分派 原理解析 - 掘金 虚方法表 JVM 栈帧&am…

假期day5

TCP UDP区别 共同点&#xff1a;都是属于传输层的协议 TCP&#xff1a;稳定。面向连接的&#xff0c;有可靠的数据传输服务。传输过程中数据无误&#xff0c;无丢失&#xff0c;无失序&#xff0c;无重复。传输效率低&#xff0c;耗费资源多。数据收发不同步&#xff0c;有沾…

C++基础入门之引用

目录 一.引用 1.1引用和取地址 1.2 别名和原名的区别 1.3 引用的用法 1.31 做参数 1.311 输出型参数&#xff1a;形参改变实参 1.312 可以减少拷贝&#xff0c;增加效率 1.32 引用的约定 1. 引用必须初始化 2. 引用定义后&#xff0c;不能改变指向 4. 给指针取别名 1.33…

『运维备忘录』之 HTTP 响应状态码速查

运维人员不仅要熟悉操作系统、服务器、网络等只是&#xff0c;甚至对于开发相关的也要有所了解。很多运维工作者可能一时半会记不住那么多命令、代码、方法、原理或者用法等等。这里我将结合自身工作&#xff0c;持续给大家更新运维工作所需要接触到的知识点&#xff0c;希望大…

4核8g服务器能支持多少人访问?- 腾讯云

腾讯云轻量4核8G12M轻量应用服务器支持多少人同时在线&#xff1f;通用型-4核8G-180G-2000G&#xff0c;2000GB月流量&#xff0c;系统盘为180GB SSD盘&#xff0c;12M公网带宽&#xff0c;下载速度峰值为1536KB/s&#xff0c;即1.5M/秒&#xff0c;假设网站内页平均大小为60KB…

2024年【上海市安全员C3证】考试及上海市安全员C3证新版试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2024年【上海市安全员C3证】考试及上海市安全员C3证新版试题&#xff0c;包含上海市安全员C3证考试答案和解析及上海市安全员C3证新版试题练习。安全生产模拟考试一点通结合国家上海市安全员C3证考试最新大纲及上海市…