java 牛客网之[动态规划 中等]NC6 【模板】二维前缀和

java 牛客网之[动态规划 中等]NC6 【模板】二维前缀和

题目的链接在这里：https://www.nowcoder.com/practice/99eb8040d116414ea3296467ce81cbbc

目录

• 题目大意
• 一、示意图
• 二、解题思路
• • 前缀和固定套路

---

题目大意 给你一个 n 行 m 列的矩阵 A ，下标从1开始。

接下来有 q 次查询，每次查询输入 4 个参数 x1 , y1 , x2 , y2

请输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和，

---

一、示意图

二、解题思路

前缀和固定套路

前缀和固定套路

代码如下：

import java.util.*;

public class  Main{
   public static void main(String[] args) {
        
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int q=sc.nextInt();
        //然后创建一个数组 用来存数据
        long[][] target=new long[n][m];
        //然后一个对应合 试试看能不能求
        long[][] sum=new long[n][m];
        //然后开始输入
        for(int i=0;i0){
            q--;
            int x1=sc.nextInt();
            int y1=sc.nextInt();
            int x2=sc.nextInt();
            int y2=sc.nextInt();
            //然后就用那个sum表示的是 0 0到 i j的方法就方程进行拆分
            //需要的值等于   sum[x2][y2]-sum[x2][y1]-sum[x1][y2]+sum[x1][y1] 画图可知
            //结果图分析可知
            //需要的是-2 sum[x2-1][y2-1]-sum[x2-1][y1-1]-sum[x1-1][y2-1]+sum[x1-1][y1-1]
            if(x1==1&&y1==1){
                System.out.println(sum[x2 - 1][y2 - 1]);
                continue;
            }
            if(x1==1){
                //如果是x1在第一层的话
                System.out.println(sum[x2 - 1][y2 - 1] - sum[x2 - 1][y1 - 2] );
                continue;

            }
            if(y1==1){
                System.out.println(sum[x2 - 1][y2 - 1]  - sum[x1 - 2][y2 - 1] );
                continue;
            }
                System.out.println(sum[x2 - 1][y2 - 1] - sum[x2 - 1][y1 - 2] - sum[x1 - 2][y2 - 1] + sum[x1 - 2][y1 - 2]);
            
        }


    }
}