题解 P1719 【最大加权矩形】

· · 题解

题外话：

n久没有写题解了，咕值掉的不爱掉了，赶紧写一个题解加一下QωQ

正文：

这道题其实还是满水的。

首先呢。。。

你要算一个矩阵的内部元素和，比如说下图中的红色部分：

\ \ \ 0\ -2\ -7\ \ \ \ \ \ \ 0 \ \ \ 9\ \ \ \ \ \ \color{red}2\ -6\ \ \ \ \ \ \ \color{black}2 -4\ \ \ \ \ \ \color{red}1\ -4\ \ \ \ \ \ \ \color{black}1 -1\ \ \ \ \ \ 8\ \ \ \ \ \ 0\ \ -2

其实可以等同于蓝色部分：

\color{blue}\ \ \ 0\ -2\ -7\ \ \ \ \ \ \ \color{black}0 \color{blue}\ \ \ 9\ \ \ \ \ \ 2\ -6\ \ \ \ \ \ \ \color{black}2 \color{blue}-4\ \ \ \ \ \ 1\ -4\ \ \ \ \ \ \ \color{black}1 -1\ \ \ \ \ \ 8\ \ \ \ \ \ 0\ \ -2

减去绿色部分

\color{green}\ \ \ 0\ -2\ -7\ \ \ \ \ \ \ \color{black}0 \ \ \ 9\ \ \ \ \ \ 2\ -6\ \ \ \ \ \ \ \color{black}2 -4\ \ \ \ \ \ 1\ -4\ \ \ \ \ \ \ \color{black}1 -1\ \ \ \ \ \ 8\ \ \ \ \ \ 0\ \ -2

再减去绿色部分

\color{green}\ \ \ 0\color{black}\ -2\ -7\ \ \ \ \ \ \ 0 \color{green}\ \ \ 9\color{black}\ \ \ \ \ \ 2\ -6\ \ \ \ \ \ \ 2 \color{green}-4\color{black}\ \ \ \ \ \ 1\ -4\ \ \ \ \ \ \ 1 -1\color{black}\ \ \ \ \ \ 8\ \ \ \ \ \ 0\ \ -2

加上黄色部分

\color{yellow}\ \ \ 0\color{black}\ -2\ -7\ \ \ \ \ \ \ 0 \ \ \ 9\ \ \ \ \ \ 2\ -6\ \ \ \ \ \ \ \color{black}2 -4\ \ \ \ \ \ 1\ -4\ \ \ \ \ \ \ \color{black}1 -1\ \ \ \ \ \ 8\ \ \ \ \ \ 0\ \ -2

就变成了上面的红色部分。

那么假设红色部分左上角坐标为(x1,y1)，右下角为(x2,y2)，设sum[x][y]表示从(1,1)加到(x,y)的和，那么红色部分就是：

sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]

(可以自己理解一下)

那么sum[x][y]要怎么求呢？

其实就是x这一行到y的前缀和加上sum[x-1][y]就Ok啦~~

可以自己理解一下（应该很好理解吧）

然后呢，再用4个变量循环判断坐标，然后求最大值即可。

代码如下：

#include<iostream>
using namespace std;
int n;
int a[130][130];//存储题目中的矩阵
int sum[130][130];
int qz[130][130];//qz[i][j]指的是第i行到j的前缀和
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            qz[i][j]=qz[i][j-1]+a[i][j];//求前缀和
            sum[i][j]=qz[i][j]+sum[i-1][j];//计算sum
        }
    }
    int mx=-99999999;//存储答案
    for(int x1=1;x1<=n;x1++){
        for(int y1=1;y1<=n;y1++){
            for(int x2=1;x2<=n;x2++){
                for(int y2=1;y2<=n;y2++){
                    if(x2<x1 || y2<y1) continue;//如果左上角比右下角还要大，就不用求了，下一个
                    mx=max(mx,sum[x2][y2]+sum[x1-1][y1-1]-sum[x2][y1-1]-sum[x1-1][y2]);//求最大值
                }
            }
        }
    }
    cout<<mx;//输出
    return 0;
}