P1719题解

· · 个人记录

P1719 最大加权矩形

暴力思想

不多说了，O(n^6) 六重循环，枚举(x1, y1), (x2, y2)，最后再枚举矩阵元素，求和。

然鹅。。。

可见，这题有效率更高的算法。 ## 上正解 这题其实是一个二维前缀和的模板。 首先， 你要求一个内部矩阵元素的和，比如这个： $0~~~-2~~~-7~~~~~~~0 9~~~~~~~~2~~~-6~~~~~~~2 -4~~~~~1~~~-4~~~~~~~1 -1 ~~~~~\textcolor{blue}{8}~~~~~~~~\textcolor{blue}{0}~~-2

就等于：

\textcolor{blue}{0}~~~\textcolor{blue}{-2}~~~\textcolor{blue}{-7}~~~~~~~0 \textcolor{blue}{9}~~~~~~~~\textcolor{blue}{2}~~~\textcolor{blue}{-6}~~~~~~~2 \textcolor{blue}{-4}~~~~~\textcolor{blue}{1}~~~\textcolor{blue}{-4}~~~~~~~1 \textcolor{blue}{-1} ~~~~~\textcolor{blue}{8}~~~~~~~~\textcolor{blue}{0}~~-2

减掉

\textcolor{blue}{0}~~~-2~~~-7~~~~~~~0 \textcolor{blue}{9}~~~~~~~~2~~~-6~~~~~~~2 \textcolor{blue}{-4}~~~~~1~~~-4~~~~~~~1 \textcolor{blue}{-1} ~~~~~8~~~~~~~~0~~-2

再减去：

\textcolor{blue}{0}~~~\textcolor{blue}{-2}~~~\textcolor{blue}{-7}~~~~~~~0 \textcolor{blue}{9}~~~~~~~~\textcolor{blue}{2}~~~\textcolor{blue}{-6}~~~~~~~2 \textcolor{blue}{-4}~~~~~\textcolor{blue}{1}~~~\textcolor{blue}{-4}~~~~~~~1 -1 ~~~~~8~~~~~~~~0~~-2

但由于左边的三个数被重复减了两遍，所以最后还要加上：

\textcolor{blue}{0}~~~-2~~~-7~~~~~~~0 \textcolor{blue}{9}~~~~~~~~2~~~-6~~~~~~~2 \textcolor{blue}{-4}~~~~~1~~~-4~~~~~~~1 -1 ~~~~~8~~~~~~~~0~~-2

显而易见了，在求(x1, x2)到(y1, y2)的子矩阵元素时，可以直接用

辣么…… $d[i][j]$咋求？ 显然， $d[i][j]=d[i-1][j]+d[i][j-1]+a[i][j]-d[i-1][j-1]; 
int n, a[125][125], d[125][125], maxn=-0x3f3f3f3f, s[125][125];
void input(){
    scanf("%d", &n);
    for (int i=1; i<=n; i++){
        for (int j=1; j<=n; j++){
            scanf("%d", &a[i][j]);
            d[i][j]=d[i-1][j]+d[i][j-1]+a[i][j]-d[i-1][j-1];
        }
    }
}

void work(){
    for (int x1=1; x1<=n; x1++){
        for (int y1=1; y1<=n; y1++){
            for (int x2=x1; x2<=n; x2++){
                for (int y2=y1; y2<=n; y2++){
                    maxn=max(maxn, d[x2][y2]+d[x1-1][y1-1]-d[x2][y1-1]-d[x1-1][y2]);
                }
            }
        }
    }
    printf("%d\n", maxn);
}