HDU1559（二维前缀和模板 Java&C++）-白红宇

HDU1559（二维前缀和模板 Java&C++）

阅读量：390 次

发布时间：2019-03-05

本文共 3303 字，大约阅读时间需要 11 分钟。

给定一个m×n的整数矩阵，目标是找到一个x×y的子矩阵，使其元素的和最大。以下是详细的解决方案：

二维前缀和方法是高效地解决此问题的有效方法。前缀和数组dp[i][j]表示前i行、前j列的矩阵元素的和，计算公式为：[ dp[i][j] = matrix[i][j] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] ]

在遍历每个dp[i][j]时，当i ≥ x且j ≥ y时，计算当前dp[i][j]对应的x×y子矩阵的和：[ submatrix_sum = dp[i][j] - dp[i - x][j] - dp[i][j - y] + dp[i - x][j - y] ]并且跟踪当前最大的子矩阵和。

以下是实现步骤：

初始化dp数组，大小为(m+1)×(n+1)，初始化为0。

遍历每个i和j（从1到m和n），计算dp[i][j]。

当i ≥ x且j ≥ y时，计算子矩阵的和，更新最大值。

输出每组测试的最大和。

该方法在计算效率和代码简洁性之间找到平衡，适用于大规模矩阵。

import java.util.Scanner;public class HDU1559 {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int T = sc.nextInt();        for (int i = 0; i < T; i++) {            int m = sc.nextInt();            int n = sc.nextInt();            int x = sc.nextInt();            int y = sc.nextInt();            int[][] dp = new int[m + 1][n + 1];            int maxSub = 0;            for (int i1 = 1; i1 <= m; i1++) {                for (int j1 = 1; j1 <= n; j1++) {                    // 首先读取元素                    if (i1 == 1 || j1 == 1) {                        dp[i1][j1] = (i1 == 1 && j1 == 1) ? sc.nextInt() : 0;                    } else {                        int current = sc.nextInt();                        dp[i1][j1] = current + dp[i1 - 1][j1] + dp[i1][j1 - 1] - dp[i1 - 1][j1 - 1];                        if (i1 >= x && j1 >= y) {                            // 计算当前dp[i][j]对应的x*y子矩阵的和                            int sub = dp[i1][j1] - dp[i1 - x][j1] - dp[i1][j1 - y] + dp[i1 - x][j1 - y];                            if (sub > maxSub) {                                maxSub = sub;                            }                        }                    }                }            }            System.out.println(maxSub);        }    }}

#include 
   
    #include 
    
     #include 
     
      using namespace std;int main() {    int T;    int m, n, x, y;    cin >> T;    for (; T--; ) {        cin >> n >> m >> x >> y;        int maxn = 0;        int dp[m + 1][n + 1];        for (int i = 1; i <= m; i++) {            for (int j = 1; j <= n; j++) {                int current;                if (i == 1 && j == 1) {                    current = 0;                } else if (i == 1) {                    current = dp[i][j - 1];                } else if (j == 1) {                    current = dp[i - 1][j];                } else {                    // 读取输入                    if (i == 1 && j == 1) {                        cin >> current;                    } else {                        int a = 0;                        if (i > 1) a = dp[i - 1][j];                        int b = 0;                        if (j > 1) b = dp[i][j - 1];                        int c = 0;                        if (i > 1 && j > 1) c = dp[i - 1][j - 1];                        current = (a + b - c);                    }                }                if (i > 1 || j > 1) {                    dp[i][j] = current;                } else {                    dp[i][j] = 0;                }                // 检查是否可以计算子矩阵                if (i >= x && j >= y) {                    int dx = dp[i][j] - dp[i - x][j] - dp[i][j - y] + dp[i - x][j - y];                    if (dx > maxn) {                        maxn = dx;                    }                }            }        }        cout << maxn << endl;    }}

转载地址：http://tdtzz.baihongyu.com/

你可能感兴趣的文章