当前位置: 首页 > 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 …...

OpenClaw模型微调指南:用Qwen3.5-9B-AWQ-4bit优化专业领域识别

OpenClaw模型微调指南&#xff1a;用Qwen3.5-9B-AWQ-4bit优化专业领域识别 1. 为什么需要专业领域的模型微调 上周我在处理一批医疗影像报告时&#xff0c;发现OpenClaw默认的Qwen3.5模型对专业术语的识别准确率只有60%左右。当遇到"冠状动脉CTA"这样的专业描述时&…...

新手友好:5步完成Llama3-8B对话系统的本地部署

新手友好&#xff1a;5步完成Llama3-8B对话系统的本地部署 1. 引言&#xff1a;为什么选择Llama3-8B&#xff1f; 如果你对AI对话模型感兴趣&#xff0c;想自己动手搭建一个&#xff0c;但又担心过程太复杂、电脑配置不够&#xff0c;那今天这篇文章就是为你准备的。 Meta-L…...

B站成分检测器深度解析:5大革新特性重塑评论区交互体验

B站成分检测器深度解析&#xff1a;5大革新特性重塑评论区交互体验 【免费下载链接】bilibili-comment-checker B站评论区自动标注成分油猴脚本&#xff0c;主要为原神玩家识别 项目地址: https://gitcode.com/gh_mirrors/bi/bilibili-comment-checker 在B站的海量评论互…...

低延迟内存池配置终极 checklist:12项参数+8个LLVM-Clang编译约束+3类NUMA绑定策略

第一章&#xff1a;金融级低延迟内存池的核心设计哲学在高频交易、实时风控与毫秒级行情分发等金融核心场景中&#xff0c;内存分配延迟的微小波动&#xff08;如纳秒级抖动&#xff09;可能直接导致订单执行偏差或监管合规风险。因此&#xff0c;金融级低延迟内存池并非单纯追…...

掌握智能温控:从噪音控制到散热效率的进阶指南

掌握智能温控&#xff1a;从噪音控制到散热效率的进阶指南 【免费下载链接】FanControl.Releases This is the release repository for Fan Control, a highly customizable fan controlling software for Windows. 项目地址: https://gitcode.com/GitHub_Trending/fa/FanCon…...

从模型到落地:音频降噪技术选型与工程化实战指南

1. 音频降噪技术选型的核心挑战 当你第一次把降噪模型部署到手机端时&#xff0c;大概率会遇到这样的场景&#xff1a;实验室里效果惊艳的模型&#xff0c;在实际设备上要么卡成幻灯片&#xff0c;要么耗电像开了暖手宝。这就是端侧音频降噪最现实的困境——我们必须在效果、算…...

如何用智能工具彻底改变黑苹果配置:一站式自动化解决方案的革命性突破

如何用智能工具彻底改变黑苹果配置&#xff1a;一站式自动化解决方案的革命性突破 【免费下载链接】OpCore-Simplify A tool designed to simplify the creation of OpenCore EFI 项目地址: https://gitcode.com/GitHub_Trending/op/OpCore-Simplify 在技术爱好者的世界…...

SpringBoot项目实战:5分钟搞定XXL-JOB 3.0.0与Admin控制台的本地联调

SpringBoot与XXL-JOB 3.0.0深度联调实战&#xff1a;从零搭建到避坑指南 当你需要在本地开发环境快速验证定时任务逻辑时&#xff0c;是否遇到过调度中心与业务项目无法联通的困扰&#xff1f;本文将手把手带你完成SpringBoot与XXL-JOB 3.0.0控制台的无缝对接&#xff0c;重点解…...

Stegosuite使用教程

Stegosuite 是一款专注于隐写术的跨平台工具&#xff0c;能够在不改变图像外观的前提下&#xff0c;将秘密数据&#xff08;文本、文件等&#xff09;隐藏在图像中。与加密技术不同&#xff0c;隐写术的核心是”隐藏信息的存在”&#xff0c;让第三方难以察觉数据传输的发生。主…...

如何通过CPUDoc智能调度技术提升CPU性能与能效比

如何通过CPUDoc智能调度技术提升CPU性能与能效比 【免费下载链接】CPUDoc 项目地址: https://gitcode.com/gh_mirrors/cp/CPUDoc 你是否曾因电脑运行卡顿、游戏帧率不稳或多任务处理缓慢而烦恼&#xff1f;现代CPU虽然拥有强大算力&#xff0c;但Windows系统的默认调度…...