P8218 【深进1.例1】求区间和 P1719 最大加权矩形

P8218 【深进1.例1】求区间和

题目描述

运行代码

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<int> p(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        p[i] = p[i - 1] + a[i - 1];
    }
    int m;
    cin >> m;
    for (int i = 0; i < m; ++i) {
        int l, r;
        cin >> l >> r;
        cout << p[r] - p[l - 1] << endl;
    }
    return 0;
}

代码思路

• 输入与初始化:

• 首先，程序读入一个整数 n，表示数列的长度。
• 然后，定义一个整数向量 a 存储数列元素，并通过循环按顺序读入 n 个正整数到向量 a 中。
• 初始化一个大小为 n+1 的整数向量 p（前缀和数组），所有元素初值设为0。这个数组比原数组多一位，是为了方便计算区间和时避免边界条件的特殊处理。

• 计算前缀和:

• 通过一个循环，计算从第一个元素到第 n 个元素的累计和，存储在向量 p 中。具体地，p[i] 存储的是 a[0] 到 a[i-1] 的和。这里 p[0] 设为0，是一个方便计算的基点。

• 处理区间查询:

• 接着，程序读入整数 m，表示要查询的区间数量。
• 对于每一个查询，程序读入区间左右端点 l 和 r。
• 区间和可以通过前缀和快速计算得到：区间 [l, r] 的和等于 p[r] - p[l-1]。这是因为 p[r] 是从第一个元素累加到第 r 个元素的和，而 p[l-1] 是从第一个元素累加到第 l-1 个元素的和，两者的差正好是 [l, r] 区间内所有元素的和。
• 程序输出计算得到的区间和，并继续处理下一个查询，直到所有查询完成。

实现了对任意给定区间 [l_i, r_i] 的区间和查询，时间效率高，适合处理大量区间查询的问题。

P1719 最大加权矩形

题目描述

运行代码

#include <bits/stdc++.h> 
using namespace std;  
int main() {  
    int n;  
    cin >> n;  
    vector<vector<int>> FN(n, vector<int>(n));  
    vector<vector<int>> FF(n + 1, vector<int>(n + 1, 0)); 
    for (int i = 0; i < n; ++i) {  
        for (int j = 0; j < n; ++j) {  
            cin >> FN[i][j];  
            FF[i + 1][j + 1] = FF[i][j + 1] + FF[i + 1][j] - FF[i][j] + FN[i][j];  
        }  
    }  
    int m = INT_MIN;  
    // 枚举所有可能的子矩阵边界  
    for (int i1 = 0; i1 <= n; ++i1) {  
        for (int j1 = 0; j1 <= n; ++j1) {  
            for (int i2 = i1; i2 < n; ++i2) {  
                for (int j2 = j1; j2 < n; ++j2) {  
                    int sum = FF[i2 + 1][j2 + 1] - FF[i1][j2 + 1] - FF[i2 + 1][j1] + FF[i1][j1];  
                    m = max(m, sum);  
                }  
            }  
        }  
    }  
    cout << m << endl;  
    return 0;  
}

代码思路

• 输入部分：

• 首先，代码读取矩阵的维度 n。
• 然后，定义了两个二维向量 FN 和 FF。FN 用于存储输入的原始矩阵，而 FF 用于存储前缀和矩阵。注意，FF 的维度比 FN 多1，这是因为前缀和矩阵需要多一行和一列来存储从 (0, 0) 到 (i, j) 的和。
• 接下来，代码通过两个嵌套的循环读取 FN 中的每个元素，并同时计算 FF 中的对应前缀和。

• 计算前缀和：

• 前缀和矩阵 FF 的每个元素 FF[i+1][j+1] 存储了从 (0, 0) 到 (i, j) 的矩形区域中所有元素的和。这是通过累加 FN 中相应位置的元素和从左上角、上方和左方到达 (i, j) 的前缀和来计算的。
• 使用 FF[i + 1][j + 1] = FF[i][j + 1] + FF[i + 1][j] - FF[i][j] + FN[i][j]; 这个公式，可以在 O(1) 时间复杂度内得到任何 (i, j) 位置的前缀和。

• 寻找最大加权矩形：

• 代码通过四个嵌套的循环枚举了所有可能的子矩阵边界（i1, j1 为左上角坐标，i2, j2 为右下角坐标）。
• 对于每一对边界，它使用前缀和矩阵 FF 来计算子矩阵的和。具体来说，子矩阵的和是 FF[i2 + 1][j2 + 1] - FF[i1][j2 + 1] - FF[i2 + 1][j1] + FF[i1][j1]。
• 如果这个和大于当前记录的最大和 m，则更新 m。

• 输出结果：最后，代码输出找到的最大加权矩形的和 m。
  

时间复杂度相对较低（尽管在这个特定实现中是 O(n^4)），因为它避免了直接计算每个子矩阵的和，而是通过前缀和矩阵在常数时间内得到子矩阵的和。对于非常大的矩阵，可能还需要进一步优化算法来降低时间复杂度。