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

地宫取宝dfs

在这里插入图片描述

分析:

矩阵里的每一个位置都有标记,要求的问题是:有几种方法能完成这个规定。
那么,我们只需要计算从开始(1,1)到最后(n,m)的深度优先搜索中,有几个是满足要求的即为正确答案。
有个要求是,如果一个格子中的价值比已经拿的都大,那么可以选择拿或者不拿,这里就有两种情况,一个是以手中的最大值mx做标准,另一种是以c[i][j]做标准,两种情况。

代码示例:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 55,p=1e9+7;
int n,m,k,c[N][N]; 
int dx[]={0,1};
int dy[]={1,0};
int dp[N][N][15][15];
bool inmp(int x,int y){return (x>=1&&x<=n&&y>=1&&y<=m);
}
ll dfs(int x,int y,int mx,int cnt){if(x==n&&y==m)return cnt==k;if(dp[x][y][mx][cnt]!=-1)return dp[x][y][mx][cnt];ll res=0;for(int i=0;i<2;i++){int nx=x+dx[i];int ny=y+dy[i];if(!inmp(nx,ny))continue;// 拿这个 if(c[nx][ny]>mx&&cnt<k)res=(res+dfs(nx,ny,c[nx][ny],cnt+1))%p;// 不拿这个res=(res+dfs(nx,ny,mx,cnt))%p;}return dp[x][y][mx][cnt]=res;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);memset(dp,-1,sizeof(dp));cin>>n>>m>>k;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>c[i][j];c[i][j]++;}cout<<(dfs(1,1,0,0)+dfs(1,1,c[1][1],1))%p;return 0;
}
/*可以设置状态dp[x][y][mx][cnt]表示走到(x,y),手中有cnt个宝贝且最大值为mx的方案数 */

相关文章:

地宫取宝dfs

分析&#xff1a; 矩阵里的每一个位置都有标记&#xff0c;要求的问题是&#xff1a;有几种方法能完成这个规定。 那么&#xff0c;我们只需要计算从开始(1,1)到最后(n,m)的深度优先搜索中&#xff0c;有几个是满足要求的即为正确答案。 有个要求是&#xff0c;如果一个格子中…...

Ollama 运行 Cohere 的 command-r 模型

Ollama 运行 Cohere 的 command-r 模型 0. 引言1. 安装 MSYS22. 安装 Golang3. Build Ollama4. 运行 command-r 0. 引言 Command-R Command-R 是一种大型语言模型&#xff0c;针对对话交互和长上下文任务进行了优化。它针对的是“可扩展”类别的模型&#xff0c;这些模型在高…...

2024年C语言最新经典面试题汇总(11-20)

C语言文章更新目录 C语言学习资源汇总&#xff0c;史上最全面总结&#xff0c;没有之一 C/C学习资源&#xff08;百度云盘链接&#xff09; 计算机二级资料&#xff08;过级专用&#xff09; C语言学习路线&#xff08;从入门到实战&#xff09; 编写C语言程序的7个步骤和编程…...

arm linux应用程序crash分析一般方法

目录&#xff1a; 前言一、定位问题的基本方法论1.1 生产环境下系统崩溃的日志信息示例 二、 分析这类什么都没有的app crash的一般方法论&#xff1a;附录&#xff1a;附录1 pmap -p 进程PID 查看进程的内存分配情况附录2 cat /proc/pid/maps 总结 前言 linux的应用程序app开…...

Web安全防护技术解决方案

1、防止爆破 限制请求ip访问次数&#xff0c;超过设定访问次数后&#xff0c;拒绝访问或锁定N分钟后可再次请求 2、调用短信验证码时 加入验证码采用防爆破策略 3、上传后的文件防止被猜出爬取 保存在物理磁盘可进行加密防护文件不能存储在站点目录&#xff0c;防止通过ur…...

流畅的 Python 第二版(GPT 重译)(十一)

第二十章&#xff1a;并发执行器 抨击线程的人通常是系统程序员&#xff0c;他们心中有着典型应用程序员终其一生都不会遇到的用例。[…] 在 99%的用例中&#xff0c;应用程序员可能会遇到的情况是&#xff0c;生成一堆独立线程并将结果收集到队列中的简单模式就是他们需要了解…...

Blender 3D建模要点

3d模型可以为场景的仿真模拟带来真实感&#xff0c;它还有助于更轻松地识别场景中的所有内容。 例如&#xff0c;如果场景中的所有对象都是简单的形状&#xff0c;如立方体和圆形&#xff0c;则很难在仿真中区分对象。 1、碰撞形状与视觉形状 像立方体和球体这样的简单形状&a…...

网络安全实训Day8

写在前面 网络工程终于讲完了。这星期到了网络安全技术部分。 网络安全实训-网络安全技术 网络安全概述 信息安全&#xff1a;所有保障计算机硬件、系统、软件、数据不因有意或无意的行为导致的服务中断、数据损坏或丢失等安全事件的保障技术 网络安全&#xff1a;基于计算机…...

GB28181 —— 5、C++编写GB28181设备端,完成将USB摄像头视频实时转发至GB28181服务并可播放(附源码)

被测试的USB摄像头 效果 源码说明 主要功能模拟设备端,完成注册、注销、心跳等,同时当服务端下发指令播放视频时 设备端实时读取USB摄像头视频并通过OpenCV处理后实时转ps格式后封包rtp进行推送给服务端播放。 源码 /****@remark: pes头的封装,里面的具体数据的填写已经占…...

Git工具的详细使用

一、环境说明 [rootgit ~]# getenforce Disabled [rootgit ~]# systemctl status firewalld ● firewalld.service - firewalld - dynamic firewall daemonLoaded: loaded (/usr/lib/systemd/system/firewalld.service; disabled; vendor preset: enabled)Active: inactive (d…...

【prometheus-operator】k8s监控redis

1、准备exporter https://github.com/oliver006/redis_exporter oliver006-redis_exporter-amd64.tar # 安装镜像 docker load -i oliver006-redis_exporter-amd64.tar # 上传镜像 docker tag oliver006/redis_exporter ip/monitor/redis_exporter:latest docker push ip/mo…...

外包干了4年,技术退步明显.......

先说一下自己的情况&#xff0c;大专生&#xff0c;19年通过校招进入杭州某软件公司&#xff0c;干了接近4年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落! 而我已经在一个企业干了四年的功能测…...

xbackup 备份MySQL数据库脚本

#!/bin/bash ## 方法一:将回车符(\r)替换为换行符(\n) 替换不可见字符 报错问题:shell脚本执行错误 $‘\r‘:command not found ## sed -i s/\r// xtrabackup.sh ## 备份计划任务 ## ## 每天凌晨1:30一次全量备份 ## 每天间隔1小时一次增量备份 ## 30 1 * * * backup…...

npm常用命令详解

npm&#xff08;Node Package Manager&#xff09;是Node.js的包管理器&#xff0c;它提供了大量的命令来安装、管理、发布Node.js模块和包。以下是npm常用命令的详解及示例&#xff1a; 1. 查看npm版本 命令&#xff1a;npm -v 示例&#xff1a;npm -v 将输出当前安装的npm版…...

IPV6协议之RIPNG

目录 前言&#xff1a; 一、RIPNG与RIP的区别 二、如何配置RIPNG 如何解决RIPNG环路问题呢&#xff1f; 控制RIPNG的选路 1、修改RIPNG默认优先级 2.配置接口附加开销值从而干涉RIPNG的选路 RIPNG拓展配置 1.RIPNG的认证 配置RIPNG进程下的IPsec认证&#xff1a; 配…...

JVM垃圾收集器你会选择吗?

目录 一、Serial收集器 二、ParNew收集器 三、Paralle Scavenge 四、Serial Old 五、Parallel Old 六、CMS收集器 6.1 CMS对处理器资源非常敏感 6.2 CMS容易出现浮动垃圾 6.3 产生内存碎片 七、G1 收集器 八、如何选择合适的垃圾收集器 JVM 垃圾收集器是Java虚…...

游戏防沉迷系统相关内容

网站地址&#xff1a;网络游戏防沉迷实名认证系统 PHP代码&#xff1a; 创建对应文件&#xff0c;在需要的位置get传参请求即可&#xff0c;具体参数参考 网络游戏防沉迷实名认证系统接口对接技术规范v2.0 1、上传信息 <?php $url "https://wlc.nppa.gov.cn/test…...

每日OJ题_牛客_JD1 年终奖(动态规划)

目录 牛客_JD1 年终奖 解析代码 牛客_JD1 年终奖 年终奖_牛客题霸_牛客网 解析代码 #include <vector> class Bonus { public: int getMost(vector<vector<int> > board) {int m board.size(), n board[0].size();vector<vector<int>> dp(m…...

深度学习 tablent表格识别实践记录

下载代码&#xff1a;https://github.com/asagar60/TableNet-pytorch 下载模型&#xff1a;https://drive.usercontent.google.com/download?id13eDDMHbxHaeBbkIsQ7RSgyaf6DSx9io1&exportdownload&confirmt&uuid1bf2e85f-5a4f-4ce8-976c-395d865a3c37 原理&#…...

深度学习 线性神经网络(线性回归 从零开始实现)

介绍&#xff1a; 在线性神经网络中&#xff0c;线性回归是一种常见的任务&#xff0c;用于预测一个连续的数值输出。其目标是根据输入特征来拟合一个线性函数&#xff0c;使得预测值与真实值之间的误差最小化。 线性回归的数学表达式为&#xff1a; y w1x1 w2x2 ... wnxn …...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

GraphQL 实战篇:Apollo Client 配置与缓存

GraphQL 实战篇&#xff1a;Apollo Client 配置与缓存 上一篇&#xff1a;GraphQL 入门篇&#xff1a;基础查询语法 依旧和上一篇的笔记一样&#xff0c;主实操&#xff0c;没啥过多的细节讲解&#xff0c;代码具体在&#xff1a; https://github.com/GoldenaArcher/graphql…...

MLP实战二:MLP 实现图像数字多分类

任务 实战&#xff08;二&#xff09;&#xff1a;MLP 实现图像多分类 基于 mnist 数据集&#xff0c;建立 mlp 模型&#xff0c;实现 0-9 数字的十分类 task: 1、实现 mnist 数据载入&#xff0c;可视化图形数字&#xff1b; 2、完成数据预处理&#xff1a;图像数据维度转换与…...