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

*地宫取宝c++

题目

输入样例1:

2 2 2
1 2
2 1

输出样例1:

2

输入样例2:

2 3 2
1 2 3
2 1 5

输出样例2:

14
思路

题目说从入口开始,只能向右或向下行走到达右下角,类似“摘花生”这道题的模型。题目又说只有当格子里的宝贝价值比小明手中任意宝贝价值都大,小明就可以拿起它,也就说拿到的宝贝价值严格单调递增,是“单调递增子序列”的模型。

状态表示
        那用几维才能表示一个状态呢?首先,需要用 i, j 来表示从起点走到 (i, j) 这个格子的所有路径方案数;然后,需要用ki来表示从起点走到(i, j)这个格子拿了多少个物品;最后,由于拿到的宝贝价值要严格单调递增,因此需要用C表示拿到的最后一个物品的价值。

        那为什么我们不用最后一个物品的坐标来表示状态呢,通过坐标也可以得到最后一个物品的价值啊?因为有50 x 50个坐标,并且是这样做会使一个状态表示的维数达到五维,时间复杂度也会增加。题目中取到宝贝的价值有限(0≤Ci≤12),因此可以用C代表最后取到的宝贝的最大值即可,这样可以将维数降到四维。

        综上所述,我们可以将集合f[i][j][ki][c]定义为所有从起点走到(i,j),且已经取了ki件物品,且最后一件物品的价值是C的合法方案的集合。集合属性为满足集合定义的方案数总和。

状态计算:
由于到达(i, j)这个点只能从左边或上边来,因此可以将集合划分为所有最后一步是从上往下走的走法的集合和所有最后一步是从左往右走的走法的集合。而对于所有最后一步是从上往下走的走法的集合,又可以划分为取不取(i, j)这个格子的宝贝这两个小的集合,当要取(i, j)这个格子的宝贝时,说明这个格子里宝贝价值value比前面拿到的任何宝贝的价值都大,并且,根据集合定义,f[i][j][ki][c]存的是最后一件物品的价值是c的合法方案的集合,因此,当枚举c时,若要取(i, j)这个格子的宝贝还需要满足value等于c。

边界处理
        需要注意的是,由于宝贝的价值可能为0,当左上角格子的的宝贝价值为0时,不拿可以表示为f[1][1][0][0] = 1,但下一步(向右或向下走)遇到一个格子的宝贝价值为0,就不能拿了,因为题目要求拿到的宝贝价值要严格单调递增;而实际上,若没有拿左上角格子价值为0的宝贝,在下一步遇到一个价值为0的宝贝是可以选择拿或不拿的。

        对此,我们可以将所有格子里宝贝的价值都加上1,宝贝价值区间变成1≤Ci≤13;当c为0时表示还没有拿过任何一件宝贝,“最后一个物品价值为0”。这样处理后,当左上角格子的的宝贝价值为1时,不拿可以表示为f[1][1][0][0] = 1,当下一步(向右或向下走)遇到一个格子的宝贝价值为1,就可以选择拿或不拿了。

        int 范围为2.1 x 10^9,因此val最多加两个数就要取模了。

代码
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1000000007, N = 55;
int a[N][N], f[N][N][13][14];
int n, m, k, res;int main()
{cin >> n >> m >> k;for (int i = 1; i <= n; i ++){for (int j = 1; j <= m; j ++){cin >> a[i][j];a[i][j] ++;}}int res = 0;f[1][1][1][a[1][1]] = 1, f[1][1][0][0] = 1;for (int i = 1; i <= n; i ++){for (int j = 1; j <= m; j ++){if (i == 1 && j == 1) continue;for (int ki = 0; ki <= k; ki ++){for (int value = 0; value <= 13; value ++){int &val = f[i][j][ki][value];//不能选(i, j)这个格子里的宝贝//从上往下走,并且不取(i, j)上的宝贝的方案数val = (val + f[i - 1][j][ki][value]) % MOD;//从左往右走,并且不取(i, j)上的宝贝的方案数val = (val + f[i][j - 1][ki][value]) % MOD;if (ki > 0 && value == a[i][j]){for (int c = 0; c < value; c ++){//从前面的状态中选价值c < value并且选了ki - 1件的fval = (val + f[i - 1][j][ki - 1][c]) % MOD;val = (val + f[i][j - 1][ki - 1][c]) % MOD;}}}}}}for (int i = 1; i <= 13; i ++) res = (res + f[n][m][k][i]) % MOD;cout << res;return 0;
}

感觉DP就是根据集合定义打好表,算出全部的状态的值,然后查询表中符合题目要求的状态值。

相关文章:

*地宫取宝c++

题目 输入样例1&#xff1a; 2 2 2 1 2 2 1输出样例1&#xff1a; 2输入样例2&#xff1a; 2 3 2 1 2 3 2 1 5输出样例2&#xff1a; 14 思路 题目说从入口开始&#xff0c;只能向右或向下行走到达右下角&#xff0c;类似“摘花生”这道题的模型。题目又说只有当格子里的宝…...

同态滤波算法详解

同态滤波是一种用于增强图像的方法&#xff0c;特别适用于去除图像中的照明不均和阴影。该算法基于照射反射模型&#xff0c;将图像分解为两个分量&#xff1a;照射分量&#xff08;illumination component&#xff09;和反射分量&#xff08;reflection component&#xff09;…...

财务管理系统报账和挂账分别什么区别!报销又是什么【第三期】

前言 已经写了两期 财务管理系统之saas多租户架构是什么以及分库分表以及如何选择分布式事务方案 【程序员聊业务】财务管理系统之模块分类 报账和挂账概念 报账是指企业或个人因业务需要而发生的各项费用支出&#xff0c;在支付后&#xff0c;需要将相关的票据、凭证等提交…...

最少刷题数

最少刷题数 题目分析 对于每一名同学计算还需要再刷多少题才能保证刷题数比他多的人数不超过刷题数比他少的学生人数。我们可以考虑统计每一个分数的前缀和数组&#xff0c;sum[i]表示当前学生中&#xff0c;刷题数小于等于i的人数。那么对于学生i的刷题数a[i]&#xff0c;su…...

Python刘诗诗

写在前面 刘诗诗在电视剧《一念关山》中饰演了女主角任如意&#xff0c;这是一个极具魅力的女性角色&#xff0c;她既是一位有着高超武艺和智慧的女侠士&#xff0c;也曾经是安国朱衣卫前左使&#xff0c;身怀绝技且性格坚韧不屈。剧中&#xff0c;任如意因不满于朱衣卫的暴行…...

探索ChatGPT在软件架构师工作中的应用

随着人工智能技术的不断发展&#xff0c;自然语言处理模型如OpenAI的ChatGPT已经成为了解决各种实际问题的强大工具之一。在软件架构师这个领域&#xff0c;ChatGPT也有着广泛的应用。本文将探讨软件架构师如何有效地利用ChatGPT来解决问题和提高工作效率。 ChatGPT简介 Chat…...

pytest--allure报告中添加用例详情

前言 前面介绍了如何生成allure的报告&#xff0c;看着allure的页面非常好看&#xff0c;但是感觉少了一些内容&#xff0c;allure还可以增加一些用例详情内容&#xff0c;这样让我们的报告看着更加绚丽。 allure增加用例详情 我们可以在报告测试套件中增加用例详情内容。 …...

【深度学习笔记】9_5 多尺度目标检测

注&#xff1a;本文为《动手学深度学习》开源内容&#xff0c;部分标注了个人理解&#xff0c;仅为个人学习记录&#xff0c;无抄袭搬运意图 9.5 多尺度目标检测 在9.4节&#xff08;锚框&#xff09;中&#xff0c;我们在实验中以输入图像的每个像素为中心生成多个锚框。这些…...

Linux--vim

一.什么是vim Vim&#xff08;Vi IMproved&#xff09;是一种文本编辑器&#xff0c;通常在Linux和其他类Unix操作系统中使用。它是Vi编辑器的增强版本&#xff0c;提供了更多的功能和定制选项。Vim具有强大的文本编辑和编程功能&#xff0c;支持语法高亮、代码折叠、宏录制、…...

FreeRTOS操作系统学习——中断管理

中断管理介绍 嵌入式实时系统需要对整个系统环境产生的事件作出反应。这些事件对处理时间和响应时间都有不同的要求。事件通常采用中断方式检测&#xff0c;中断服务例程(ISR)中的处理量应当越短越好。ISR是在内核中被调用的&#xff0c; ISR执行过程中&#xff0c;用户的任务…...

DHCP中继实验(思科)

华为设备参考&#xff1a;DHCP中继实验&#xff08;华为&#xff09; 一&#xff0c;技术简介 DHCP中继&#xff0c;可以实现在不同子网和物理网段之间处理和转发DHCP信息的功能。如果DHCP客户机与DHCP服务器在同一个物理网段&#xff0c;则客户机可以正确地获得动态分配的IP…...

基于SpringBoot的“心灵治愈交流平台”的设计与实现(源码+数据库+文档+PPT)

基于SpringBoot的“心灵治愈交流平台”的设计与实现&#xff08;源码数据库文档PPT) 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SpringBoot 工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 系统功能界面图 登录、用户注册界面图 心灵专…...

【SpringBoot】自定义工具类实现Excel数据新建表存入MySQL数据库

&#x1f3e1;浩泽学编程&#xff1a;个人主页 &#x1f525; 推荐专栏&#xff1a;《深入浅出SpringBoot》《java对AI的调用开发》 《RabbitMQ》《Spring》《SpringMVC》《项目实战》 &#x1f6f8;学无止境&#xff0c;不骄不躁&#xff0c;知行合一 文章目录 …...

Retelling|Facebook1

录音 Facebook 1 Retelling|Facebook1 复述转写 Today Im totally going to talk about Facebook. The aspects of this (its)rising fame and fortune, and the rise (小停顿)in(rising) fame and fortune of s founder Mark Zuckerberg, Mark Zuckerberg created this plat…...

【2024-03-12】设计模式之模板模式的理解

实际应用场景&#xff1a;制作月饼 过程描述&#xff1a; 一开始&#xff0c;由人工制作月饼&#xff0c; 第一个&#xff1a;根据脑子里面月饼的形状&#xff0c;先涅出月饼的形状&#xff0c;然后放入面粉和馅料把开口合并起来。 第二个&#xff1a;根据脑子里面月饼的形状&…...

Transformer模型引领NLP革新之路

在不到4 年的时间里&#xff0c;Transformer 模型以其强大的性能和创新的思想&#xff0c;迅速在NLP 社区崭露头角&#xff0c;打破了过去30 年的记录。BERT、T5 和GPT 等模型现在已成为计算机视觉、语音识别、翻译、蛋白质测序、编码等各个领域中新应用的基础构件。因此&#…...

【Kotlin】运算符函数、解构函数、中缀函数

1 一元运算符 1.1 符号和函数 符号函数aa.unaryPlus()-aa.unaryMinus()!aa.not()aa.dec()a--a.inc() 1.2 案例 fun main() {var stu Student("Tom", 13)println(-stu) // 打印: [moT, 31] }class Student(var name: String, var age: Int) {operator fun unaryM…...

springboot268码头船只货柜管理系统

码头船只出行和货柜管理系统的设计与实现 摘要 针对于码头船只货柜信息管理方面的不规范&#xff0c;容错率低&#xff0c;管理人员处理数据费工费时&#xff0c;采用新开发的码头船只货柜管理系统可以从根源上规范整个数据处理流程。 码头船只货柜管理系统能够实现货柜管理…...

Java面试题11MySQL之执行计划到事务及慢查询

你对MySQL执行计划怎么看 执行计划就是SQL的执行查询的顺序&#xff0c;以及如何使用索引查询&#xff0c;返回的结果集的行数 在MySQL中&#xff0c;我们可以通过explain命令来查看执行计划。其语法如下&#xff1a; EXPLAIN SELECT * FROM table_name WHERE conditions;在…...

算法时空复杂度分析:大O表示法

文章目录 前言大O表示法3个时间复杂度分析原则常见的时间复杂度量级空间复杂度参考资料 前言 算法题写完以后&#xff0c;面试官经常会追问一下你这个算法的时空复杂度是多少&#xff1f;&#xff08;好像作为一名算法工程师&#xff0c;我日常码代码的过程中&#xff0c;并没…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

《Docker》架构

文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器&#xff0c;docker&#xff0c;镜像&#xff0c;k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...

DAY 26 函数专题1

函数定义与参数知识点回顾&#xff1a;1. 函数的定义2. 变量作用域&#xff1a;局部变量和全局变量3. 函数的参数类型&#xff1a;位置参数、默认参数、不定参数4. 传递参数的手段&#xff1a;关键词参数5 题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一…...

【笔记】AI Agent 项目 SUNA 部署 之 Docker 构建记录

#工作记录 构建过程记录 Microsoft Windows [Version 10.0.27871.1000] (c) Microsoft Corporation. All rights reserved.(suna-py3.12) F:\PythonProjects\suna>python setup.py --admin███████╗██╗ ██╗███╗ ██╗ █████╗ ██╔════╝…...

Heygem50系显卡合成的视频声音杂音模糊解决方案

如果你在使用50系显卡有杂音的情况&#xff0c;可能还是官方适配问题&#xff0c;可以使用以下方案进行解决&#xff1a; 方案一&#xff1a;剪映替换音色&#xff08;简单适合普通玩家&#xff09; 使用剪映换音色即可&#xff0c;口型还是对上的&#xff0c;没有剪映vip的&…...