#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
输出:
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();
}
}
}
文章来源: https://blog.51cto.com/u_15488507/5857014
特别声明:以上内容(图片及文字)均为互联网收集或者用户上传发布,本站仅提供信息存储服务!如有侵权或有涉及法律问题请联系我们。
举报