返回

#yyds干货盘点# 动态规划专题:二维差分

发布时间:2023-11-20 03:06:32 199

1.简述:

描述

给你一个n行m列的矩阵,下标从1开始。接下来有q次操作,每次操作输入5个参数x1, y1, x2, y2, k表示把以(x1, y1)为左上角,(x2,y2)为右下角的子矩阵的每个元素都加上k,请输出操作后的矩阵。

输入描述:

第一行包含三个整数n,m,q.接下来n行,每行m个整数,代表矩阵的元素

接下来q行,每行5个整数x1, y1, x2, y2, k,分别代表这次操作的参数

     

输出描述:

输出n行,每行m个数,每个数用空格分开,表示这个矩阵。

示例1

输入:

2 3 4
1 2 3
4 5 6
1 1 2 2 3
1 2 2 3 -1
1 1 1 3 4
1 1 2 1 1

输出:

9 8 6
8 7 5

2.代码实现:

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();
//存放数组元素
int[][] arr=new int[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
arr[i][j]=sc.nextInt();
}
}
//存放增量
long[][] delta=new long[n+2][m+2];
//q次操作
while(q-->0){
int x1=sc.nextInt();
int y1=sc.nextInt();
int x2=sc.nextInt();
int y2=sc.nextInt();
int k=sc.nextInt();
//进行差分处理
delta[x1][y1]+=k;
delta[x1][y2+1]-=k;
delta[x2+1][y1]-=k;
delta[x2+1][y2+1]+=k;
}

//计算前缀和还原对应元素的增量
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
delta[i+1][j+1]+=delta[i][j+1];
}
}

for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
delta[i+1][j+1]+=delta[i+1][j];
System.out.print(delta[i+1][j+1]+arr[i][j]+" ");
}
System.out.println();
}


}
}

 

特别声明:以上内容(图片及文字)均为互联网收集或者用户上传发布,本站仅提供信息存储服务!如有侵权或有涉及法律问题请联系我们。
举报
评论区(0)
按点赞数排序
用户头像
精选文章
thumb 中国研究员首次曝光美国国安局顶级后门—“方程式组织”
thumb 俄乌线上战争,网络攻击弥漫着数字硝烟
thumb 从网络安全角度了解俄罗斯入侵乌克兰的相关事件时间线
下一篇
零拷贝技术 2023-11-20 00:02:49