【Leetcode每日一题】DP35 二维前缀和(难度⭐⭐)(26)

1. 题目解析

题目链接:DP35 【模板】二维前缀和

这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。

核心在于计算题目所给二维区间数组元素和返回即可。

2. 算法原理

和上题了类似的方法,使用dp数组来保存[1,1]到[x,y]的和,这里不过多赘述,之间看代码更容易理解。

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> arr(n + 1, vector<int>(m + 1));
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> arr[i][j];

    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
    
    int x1, x2, y1, y2;
    while(q--)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

The Last

嗯,就是这样啦,文章到这里就结束啦,真心感谢你花时间来读。

觉得有点收获的话,不妨给我点个吧!

如果发现文章有啥漏洞或错误的地方,欢迎私信我或者在评论里提醒一声~ 

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

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

相关文章

科普【1】:web3.0初探,不懂技术也能看懂。

Hi&#xff0c;我是贝格前端工场&#xff0c;本期来科普一下web3这个概念&#xff0c;力争讲的浅显易懂。 一、什么是web3及其特征 Web3是指第三代互联网&#xff0c;也被称为分布式互联网或区块链互联网。它是对传统互联网的一种进化和扩展&#xff0c;旨在提供更加去中心化、…

为什么中小APP开发者要选择聚合SDK广告变现服务?

广告变现听起来容易&#xff0c;但要在不影响用户体验的情况下&#xff0c;把变现收益做到最大化&#xff0c;其实非常复杂。 对于处于行业腰部和尾部的中小APP来说&#xff0c;团队资源有限&#xff0c;要将所有的资源集中在投入到核心业务竞争力上——扩大用户规模和活跃度上…

如何测试代理IP是否可用?

目录 一、了解代理IP基础知识 二、为什么需要测试代理IP的可用性&#xff1f; 三、测试代理IP的可用性方法 使用Ping命令测试代理IP的连通性 使用curl或wget测试代理IP的可用性 编写代码测试代理IP的可用性 四、案例分析 五、总结与建议 在数字时代的今天&#xff0c;代…

.net 日志

一、Log4net 1、log4net写入文本 1、nuget引入log4net、Microsoft.Extensions.Logging.Log4Net.AspNetCore这2个 2、引入配置文件,可以直接去官网(log4net官网配置文件)复制下来,放到项目目录下面,设置成始终复制,因为这个文件最终要到我们项目运行目录下面去 3、要在pr…

3月4日工作记录

周末总结 周末花6.5k的4060ti主机到家了&#xff0c;配好了和女朋友一起玩了两天帕鲁&#xff0c;真好玩&#xff01; 玩完开始上班&#xff01; 今天&#xff0c;上午先看三篇paper&#xff0c;然后下午继续1日计划的工作 文章阅读 文章一&#xff1a;SciGLM: Training Sc…

STL——stack

目录 stack stack都有哪些接口 模拟实现一个stack stack 1. stack是一种容器适配器&#xff0c;专门用在具有后进先出操作的上下文环境中&#xff0c;其删除只能从容器的一端进行元素的插入与提取操作。 2. stack是作为容器适配器被实现的&#xff0c;容器适配器即…

【一起学习Arcade】(5):属性规则实例_计算规则

属性规则可改善地理数据库数据集的编辑体验并提高数据完整性。 这些规则均为用户定义的规则&#xff0c;可用于自动填充属性、在编辑操作期间限制无效编辑&#xff0c;以及对现有要素执行质量保证检查。 属性规则分为3类&#xff1a;计算、约束和验证。 这一篇介绍计算规则&…

HOOPS Communicator对3D大模型轻量化加载与渲染的4种解决方案

今天给大家介绍一些关于3D Web轻量化引擎HOOPS Commuicator的关键概念&#xff0c;这些概念可以帮您在HOOPS Communicator流缓存服务器之上更好地构建您自己的模型流服务器。如果您是有大型数据集&#xff0c;那么&#xff0c;使用流缓存服务器可以极大地帮助您最大限度地减少内…

PostgreSQL10.21与PostGIS3.2.3安装文档

背景&#xff1a; 公司需要在一个服务器上装一个pg数据库&#xff0c;要求和其余服务器版本尽量保持一致&#xff0c;临时拉我装一下 特别注意&#xff1a; 需要注意的地方就是因为postgresql数据库是一个空间库&#xff0c;gis行业很多都会使用这个数据库&#xff0c;我们安…

深入Kafka client

分区分配策略 客户端可以自定义分区分配策略, 当然也需要考虑分区消费之后的offset提交, 是否有冲突。 消费者协调器和组协调器 a. 消费者的不同分区策略, 消费者之间的负载均衡(新消费者加入或者存量消费者退出), 需要broker做必要的协调。 b. Kafka按照消费组管理消费者, …

HttpClient—详解、代码演示

简介&#xff1a;HttpClient 是Apache Jakarta Common 下的子项目&#xff0c;可以用来提供高效的、最新的、功能丰富的支持 HTTP 协议的客户端编程工具包&#xff0c;并且它支持 HTTP 协议最新的版本和建议&#xff0c;即可以通过HttpClient可以再Java中构建和发送Http请求。 …

将jar包打包为docker镜像

此记录一下将springboot项目的jar打包成docker镜像记录错误点。 1.将springboot项目打包成jar包 参考博客 : springboot项目打包成jar_springboot打包成jar-CSDN博客 具体打包步骤参考他的如何打包: 使用IDEA进行打包。但是我需要在我的springboot的pom.xml文件里面配置如下插…

javascript实现的星座查询

今天在这个网站http://xzxys.wiicha.com/看到查询星座幸运色的效果&#xff0c;想研究一下代码&#xff0c;结果右键禁用。后来参考了一下别人的代码&#xff0c;琢磨着先实现了一下星座查询的功能&#xff0c;输入月份和日期四位数后&#xff0c;可以查询属于哪个星座&#xf…

如何做代币分析:以 INJ 币为例

如何做代币分析&#xff1a;以 INJ 币为例 作者&#xff1a; lesleyfootprint.network 编译&#xff1a;cicifootprint.network 数据源&#xff1a;INJ 代币仪表板 &#xff08;仅包括以太坊数据&#xff09; 在加密货币和数字资产领域&#xff0c;代币分析起着至关重要的作…

网络学习:MPLS技术基础知识

目录 一、MPLS技术产生背景 二、MPLS网络组成&#xff08;基本概念&#xff09; 1、MPLS技术简介&#xff1a;Multiprotocol Lable Switching&#xff0c;多协议标签交换技术 2、MPLS网络组成 三、MPLS的优势 四、MPLS的实际应用 一、MPLS技术产生背景 1、IP采用最长掩码…

跨地域传文件时 面临的安全、效率等问题要如何解决?

近年来&#xff0c;企业在异国、异地设立分支机构的越来越多&#xff0c;在日常经营中&#xff0c;企业总部和分支机构间存在平行、垂直及互相交叉的管理模式和业务往来需求&#xff0c;因此&#xff0c;大型企业存在必然的跨地域传文件场景&#xff0c;比如跨地理域文件交换、…

6个常见的动态内存的错误和动态内存经典笔试题

和黛玉学编程..........> 这篇的代码对应知识点就在上一篇啦 常见的动态内存的错误 对NULL指针的解引用操作 void test() { int *p (int *)malloc(INT_MAX/4); *p 20; free(p); } 如果P的值是空指针就会有问题&#xff0c;所以一般都会先进行判断 对动态开辟空间的越…

【无刷电机学习】光耦HCNR200基本原理及应用(资料摘抄)

【仅作自学记录&#xff0c;不出于任何商业目的。如有侵权&#xff0c;请联系删除&#xff0c;谢谢&#xff01;】 本文摘抄翻译自&#xff1a; https://docs.broadcom.com/wcs-public/products/application-notes/application-note/331/6/av02-1333en-an_5394-16jul10.pdfhtt…

【leetcode】反转字符串 双指针

/*** param {character[]} s* return {void} Do not return anything, modify s in-place instead.*/ var reverseString function(s) {let start0;let ends.length-1;while(start<end){[s[start],s[end]][s[end],s[start]];start;end--;}return s;};双指针&#xff0c;一头…

ST32/GD32——UART串口通信

芯片选型 Ciga Device — GD32F470系列 串口通信 串口通信指的是通过串行通信接口进行数据传输的通信方式&#xff0c;通常用于短距离、低速率的数据传输。 串口通信可以使用不同的串行通信协议和接口&#xff0c;常见的串口通信协议有UART、USART、RS-232、RS-485、SPI、I…