*地宫取宝c++

news/2024/5/26 19:42:50/文章来源:https://blog.csdn.net/m0_68416190/article/details/136573279
题目

输入样例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就是根据集合定义打好表,算出全部的状态的值,然后查询表中符合题目要求的状态值。

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

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

相关文章

C语言中如何进行内存管理

主页&#xff1a;17_Kevin-CSDN博客 收录专栏&#xff1a;《C语言》 C语言是一种强大而灵活的编程语言&#xff0c;但与其他高级语言不同&#xff0c;它要求程序员自己负责内存的管理。正确的内存管理对于程序的性能和稳定性至关重要。 一、引言 C 语言是一门广泛使用的编程语…

Flink概述

1.什么是Flink 是一个框架和分布式处理引擎&#xff0c;用于对无界和有界数据流进行有状态计算。 官网&#xff1a;Flink 2.Flink的发展历史 Flink起源于一个叫作Stratosphere的项目&#xff0c;它是由3所地处柏林的大学和欧洲其他一些大学在2010~2014年共同进行的研究项目&a…

关于playbook中when条件过滤报The conditional check ‘result|failed‘ failed的问题

问题现象 在使用plabook中的when做过滤脚本如下&#xff1a; --- - hosts: realserversremote_user: roottasks:- name: Check if httpd service is runningcommand: systemctl status httpdregister: resultignore_errors: True- name: Handle failed service checkdebug:ms…

C#调用Halcon出现尝试读取或写入受保护的内存,这通常指示其他内存已损坏。System.AccessViolationException

一、现象 在C#中调用Halcon&#xff0c;出现异常提示&#xff1a;尝试读取或写入受保护的内存,这通常指示其他内存已损坏。System.AccessViolationException 二、原因 多个线程同时访问Halcon中的某个公共变量&#xff0c;导致程序报错 三、测试 3.1 Halcon代码 其中tsp_width…

sqllab第四关通关笔记

知识点&#xff1a; 判断注入点类型判断原始语句 select 1,2,3 from 表名 where id("输入") limit 0,1; 首先判断注入类型 构造id1/0 正常打印&#xff1b;字符型注入 构造id1 正常回显&#xff1b;说明不是用单引号读取输入内容 构造id1" 发生异常&#x…

Win11系统启动VMware上虚拟机蓝屏解决办法

背景 最近有在做一个项目的过程中需要使用虚拟机&#xff0c;用原来装好的的Vmware14打开虚拟机&#xff0c;直接蓝屏了&#xff0c;尝试了如下几种方法来解决&#xff0c;最好用的就是第二种&#xff0c;直接下载最新版本(在软件管家中直接下载)。 虚拟机 目前常用的虚拟机软…

初步了解序列化和反序列化

01什么是序列化和反序列化 序列化是将对象转化为字符串以便存储的一种方式。而反序列化恰好是序列化的逆过程&#xff0c;反序列化会将字符串转化为对象供程序使用。 常见的php系列化和反系列化方式主要有&#xff1a;serialize&#xff0c;unserialize&#xff1b;json_enco…

Nginx请求转发和Rewrite的URL重写及重定向的功能实现移动端和PC端前端服务转发和重定向配置。

应用场景说明一 应用系统分pc端和微信小程序&#xff0c;移动端和pc端分别申请二级子域名&#xff0c;通过Nginx域名解析匹配&#xff0c;将web访问统一转发至对应的域名请求中。部分配置如下所示&#xff1a; 1、WEB访问统一入口域名解析转发配置&#xff0c;PC端和移动端根域…

【论文阅读】OpsEval

粗糙翻译&#xff0c;如有兴趣请看原文&#xff0c;链接&#xff1a;https://arxiv.org/abs/2310.07637 摘要 信息技术&#xff08;IT&#xff09;运营&#xff08;Ops&#xff09;&#xff0c;特别是用于IT运营的人工智能&#xff08;AlOps&#xff09;&#xff0c;是保持现…

码头船只出行和货柜管理系统的设计与实现

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

Java中常见延时队列的实现方案总结

&#x1f3f7;️个人主页&#xff1a;牵着猫散步的鼠鼠 &#x1f3f7;️系列专栏&#xff1a;Java全栈-专栏 &#x1f3f7;️个人学习笔记&#xff0c;若有缺误&#xff0c;欢迎评论区指正 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&…

爬虫与DataFrame对象小小结合

import pandas as pd import requests from lxml import etree #数据请求 url"https://www.maigoo.com/brand/list_1715.html" headers{User-Agent:} #数据响应 resrequests.get(url,headersheaders) tree etree.HTML(res.text) #数据解析 titletree.xpath(.//div[c…

C语言游戏实战(4):人生重开模拟器

前言&#xff1a; 人生重开模拟器是前段时间非常火的一个小游戏&#xff0c;接下来我们将一起学习使用c语言写一个简易版的人生重开模拟器。 网页版游戏&#xff1a; 人生重开模拟器 (ytecn.com) 1.实现一个简化版的人生重开模拟器 &#xff08;1&#xff09; 游戏开始的时…

Express学习(四)

使用Express写接口 创建基本的服务器 创建API路由模块 编写GET接口 编写POST接口 CORS跨域资源共享 什么是CORS CORS由一系列HTTP响应头组成&#xff0c;这些HTTP响应头决定浏览器是否阻止前端JS代码跨域获取资源。浏览器的同源安全策略默认会阻止网页“跨域”获取资源。但如…

系统运维网络知识汇总

一、系统运维中网络方面的规划与思考 系统运维建立在网络的基础之上&#xff0c;如果没有一个相对合理的网络架构&#xff0c;恐怕系统运维做起来也不是那么的顺手。一个公司基本上都会把网络和服务器独立开来&#xff0c;划分不同的区域摆放设备&#xff0c;很多时候都是物理…

使用Java自带的VisualVM监控远程服务器部署在Docker容器中的Java项目并使用Mat在线工具排查服务器内存泄露或内存溢出的原因

事情是这样的&#xff0c;我们项目最近应业主的要求迁移到了新的服务器&#xff0c;起初一切正常&#xff0c;部署、上线、测试都没有问题&#xff0c;项目大概运行了一周的工作日时间都没出现问题&#xff0c;直到周六那天&#xff0c;项目经理打电话过来说服务器崩了&#xf…

计算机设计大赛 疲劳驾驶检测系统 python

文章目录 0 前言1 课题背景2 Dlib人脸识别2.1 简介2.2 Dlib优点2.3 相关代码2.4 人脸数据库2.5 人脸录入加识别效果 3 疲劳检测算法3.1 眼睛检测算法3.2 打哈欠检测算法3.3 点头检测算法 4 PyQt54.1 简介4.2相关界面代码 5 最后 0 前言 &#x1f525; 优质竞赛项目系列&#x…

Elasticsearch 通过索引阻塞实现数据保护深入解析

文章目录 1. 索引阻塞的种类2. 什么时候使用阻塞&#xff1f;3. 添加索引阻塞API4. 解除设置 API5. 小结6. 参考 Elasticsearch 是一种强大的搜索和分析引擎&#xff0c;被广泛用于各种应用中&#xff0c;以其强大的全文搜索能力而著称。 不过&#xff0c;在日常管理 Elastics…

八、词嵌入语言模型(Word Embedding)

词嵌入&#xff08;Word Embedding, WE&#xff09;&#xff0c;任务是把不可计算、非结构化的词转换为可以计算、结构化的向量&#xff0c;从而便于进行数学处理。 一个更官方一点的定义是&#xff1a;词嵌入是是指把一个维数为所有词的数量的高维空间&#xff08;one-hot形式…

【JAVA】CSS3伸缩盒案例、响应式布局、BFC

1.CSS3伸缩盒案例 效果&#xff1a;用伸缩盒模型 <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</title>&…