地宫取宝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
分析: 矩阵里的每一个位置都有标记,要求的问题是:有几种方法能完成这个规定。 那么,我们只需要计算从开始(1,1)到最后(n,m)的深度优先搜索中,有几个是满足要求的即为正确答案。 有个要求是,如果一个格子中…...
Ollama 运行 Cohere 的 command-r 模型
Ollama 运行 Cohere 的 command-r 模型 0. 引言1. 安装 MSYS22. 安装 Golang3. Build Ollama4. 运行 command-r 0. 引言 Command-R Command-R 是一种大型语言模型,针对对话交互和长上下文任务进行了优化。它针对的是“可扩展”类别的模型,这些模型在高…...
2024年C语言最新经典面试题汇总(11-20)
C语言文章更新目录 C语言学习资源汇总,史上最全面总结,没有之一 C/C学习资源(百度云盘链接) 计算机二级资料(过级专用) C语言学习路线(从入门到实战) 编写C语言程序的7个步骤和编程…...
arm linux应用程序crash分析一般方法
目录: 前言一、定位问题的基本方法论1.1 生产环境下系统崩溃的日志信息示例 二、 分析这类什么都没有的app crash的一般方法论:附录:附录1 pmap -p 进程PID 查看进程的内存分配情况附录2 cat /proc/pid/maps 总结 前言 linux的应用程序app开…...
Web安全防护技术解决方案
1、防止爆破 限制请求ip访问次数,超过设定访问次数后,拒绝访问或锁定N分钟后可再次请求 2、调用短信验证码时 加入验证码采用防爆破策略 3、上传后的文件防止被猜出爬取 保存在物理磁盘可进行加密防护文件不能存储在站点目录,防止通过ur…...
流畅的 Python 第二版(GPT 重译)(十一)
第二十章:并发执行器 抨击线程的人通常是系统程序员,他们心中有着典型应用程序员终其一生都不会遇到的用例。[…] 在 99%的用例中,应用程序员可能会遇到的情况是,生成一堆独立线程并将结果收集到队列中的简单模式就是他们需要了解…...
Blender 3D建模要点
3d模型可以为场景的仿真模拟带来真实感,它还有助于更轻松地识别场景中的所有内容。 例如,如果场景中的所有对象都是简单的形状,如立方体和圆形,则很难在仿真中区分对象。 1、碰撞形状与视觉形状 像立方体和球体这样的简单形状&a…...
网络安全实训Day8
写在前面 网络工程终于讲完了。这星期到了网络安全技术部分。 网络安全实训-网络安全技术 网络安全概述 信息安全:所有保障计算机硬件、系统、软件、数据不因有意或无意的行为导致的服务中断、数据损坏或丢失等安全事件的保障技术 网络安全:基于计算机…...
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年,技术退步明显.......
先说一下自己的情况,大专生,19年通过校招进入杭州某软件公司,干了接近4年的功能测试,今年年初,感觉自己不能够在这样下去了,长时间呆在一个舒适的环境会让一个人堕落! 而我已经在一个企业干了四年的功能测…...
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(Node Package Manager)是Node.js的包管理器,它提供了大量的命令来安装、管理、发布Node.js模块和包。以下是npm常用命令的详解及示例: 1. 查看npm版本 命令:npm -v 示例:npm -v 将输出当前安装的npm版…...
IPV6协议之RIPNG
目录 前言: 一、RIPNG与RIP的区别 二、如何配置RIPNG 如何解决RIPNG环路问题呢? 控制RIPNG的选路 1、修改RIPNG默认优先级 2.配置接口附加开销值从而干涉RIPNG的选路 RIPNG拓展配置 1.RIPNG的认证 配置RIPNG进程下的IPsec认证: 配…...
JVM垃圾收集器你会选择吗?
目录 一、Serial收集器 二、ParNew收集器 三、Paralle Scavenge 四、Serial Old 五、Parallel Old 六、CMS收集器 6.1 CMS对处理器资源非常敏感 6.2 CMS容易出现浮动垃圾 6.3 产生内存碎片 七、G1 收集器 八、如何选择合适的垃圾收集器 JVM 垃圾收集器是Java虚…...
游戏防沉迷系统相关内容
网站地址:网络游戏防沉迷实名认证系统 PHP代码: 创建对应文件,在需要的位置get传参请求即可,具体参数参考 网络游戏防沉迷实名认证系统接口对接技术规范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表格识别实践记录
下载代码:https://github.com/asagar60/TableNet-pytorch 下载模型:https://drive.usercontent.google.com/download?id13eDDMHbxHaeBbkIsQ7RSgyaf6DSx9io1&exportdownload&confirmt&uuid1bf2e85f-5a4f-4ce8-976c-395d865a3c37 原理&#…...
深度学习 线性神经网络(线性回归 从零开始实现)
介绍: 在线性神经网络中,线性回归是一种常见的任务,用于预测一个连续的数值输出。其目标是根据输入特征来拟合一个线性函数,使得预测值与真实值之间的误差最小化。 线性回归的数学表达式为: y w1x1 w2x2 ... wnxn …...
7步完整解决Windows 11安装失败:从错误代码到成功激活的高效指南
7步完整解决Windows 11安装失败:从错误代码到成功激活的高效指南 【免费下载链接】MediaCreationTool.bat Universal MCT wrapper script for all Windows 10/11 versions from 1507 to 21H2! 项目地址: https://gitcode.com/gh_mirrors/me/MediaCreationTool.bat…...
Win11 24H2最新绕过OOBE强制登录微软账户的3种方法(附详细步骤)
Windows 11 24H2 本地账户创建终极指南:三种可靠绕过方案详解 每次Windows大版本更新,微软总会给用户带来一些"惊喜"。这次Windows 11 24H2的OOBE(开箱体验)强制要求登录微软账户,让不少注重隐私和习惯使用…...
API统一管控平台:new-api、one-api、Grok2API、Quotio、UniAPI、Sub2API、OpenAI Router
之前写过类似文章,请参考LLM系列之API聚合平台:OpenRouter、TogetherAI、LiteLLM。 本文继续汇总几个开源API统一管控平台。 one-api 官网,开源(GitHub,30.1K Star,5.8K Fork)平台࿰…...
2026行李箱推荐别乱买!唯尊、海澜之家、森马、外交官、珉璐保罗五款横评
对于技术从业者而言,行李箱不仅是装载衣物的容器,更是保护精密电子设备、应对高频差旅与跨城迁移的可靠装备。无论是前往异地调试系统、参加技术峰会,还是举家搬迁,一个设计合理、性能可靠的行李箱能显著提升出行效率与体验。本文…...
KSA工具实战:5分钟搞定内网穿透,无需公网IP也能远程办公
KSA工具实战:5分钟搞定内网穿透,无需公网IP也能远程办公 远程办公已成为现代职场的新常态,但许多人在家访问公司内网资源时,常被复杂的网络配置和公网IP需求劝退。想象一下,周五晚上突然需要调取公司服务器上的方案文件…...
高效掌控Mem Reduct:智能多语言界面切换完全指南
高效掌控Mem Reduct:智能多语言界面切换完全指南 【免费下载链接】memreduct Lightweight real-time memory management application to monitor and clean system memory on your computer. 项目地址: https://gitcode.com/gh_mirrors/me/memreduct 你是否曾…...
QuantLib避坑指南:从编译安装到多线程优化的5个实战经验
QuantLib工程化实战:从编译优化到高并发设计的5个关键策略 在金融科技领域,QuantLib作为开源的量化金融计算库,已经成为众多机构的核心基础设施。但将QuantLib真正投入生产环境时,开发团队往往会遇到一系列工程化挑战——从复杂的…...
HTML转Figma:如何让网页设计与代码世界无缝对话
HTML转Figma:如何让网页设计与代码世界无缝对话 【免费下载链接】figma-html Convert any website to editable Figma designs 项目地址: https://gitcode.com/gh_mirrors/fi/figma-html 想象一下,你正在浏览一个设计精美的网站,突然灵…...
解决Lumerical(FDTD)中lumapi模块导入失败的完整指南
1. 为什么会出现lumapi导入失败的问题 第一次遇到import lumapi报错的时候,我也是一头雾水。明明按照官方文档安装了Lumerical软件和lumopt扩展包,怎么Python就找不到这个模块呢?后来经过多次实践和排查,发现这个问题在Windows系统…...
Azure DevOps 自托管 Agent 如何用 Service Principal 安全接入 Azure
Azure DevOps 使用服务主体配置自托管代理配置指南1. 概述2. 在 Azure AD 中创建服务主体 (SP)3. 授予 Azure DevOps 权限3.1. 组织层级:用户身份与访问级别3.2. 组织层级:Agent pools管理员3.3. 在 Linux VM 上安装和配置代理3.4. 启动并设置为系统服务…...
