Question

请问这到编程题怎么做？

1583. 国王的奖赏0
提交
提交排名
题目描述
僵尸大战结束了，你作为砍杀僵尸的战斗英雄，将获得国王给你的封地。地图里共n*n格土地，第i行第j列的土地格子里标记着f[i][j]的整数价值，可能出现负数。国王让你选择在m种方案里挑选一个，收入囊中。每一种方案都是一个矩形，第i种方案的左上角在第a[i]行第b[i]列，右下角在第c[i]行第d[i]列。请问在这些方案里，你能选到的土地总价值最大能是多少？注意你必须选一个方案，哪怕总价值是负数。
输入输出格式
输入格式
输入文件reward0.in
输入一行为正整数n，n<=1000。之后为n*n的矩阵代表每一格的价值，绝对值不超过100。之后一行为正整数m，m<=100000。接着m行每一行四个正整数a[i],b[i],c[i],d[i]，数值均在1到n之间。

输出格式
输出文件reward0.out
输出一行包含m个整数，由空格隔开。

输入输出样例
输入样例#1:
2
-2 -2
-2 -2
1
1 1 2 2

输出样例#1:
-8

Answer 1

使用二维前缀和数组求解

设pre[i][j]为二维数组f第1行第1列到第i行第j列矩形区域内的元素和

即左上角元素为f[0][0]、右下角元素为f[i-1][j-1]的矩形元素和

根据容斥原理，有f[i-1][j-1] = pre[i][j] - pre[i-1][j]- pre[i][j-1] + pre[i-1][j-1]

由此可根据如下递推关系，先得到整个二维前缀和数组pre：

pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] - f[i-1][j-1]

有了pre，只要给出左上角坐标(a,b)和右下角坐标(c,d)，就可以快速求出该矩形内元素和：

sum = pre[c][d] - pre[c][b-1] - pre[a-1][d] + pre[a-1][b-1]

C语言代码和运行结果如下：

输出符合示例，望采纳~

附源码：

#include <stdio.h>

int f[1000][1000], pre[1001][1001]; // pre为二维前缀和数组

int main() {

    int n, i, j, max = -1e8; // -100*1000*1000，最大值初始化为可能的最小值

    int m, a, b, c, d, sum;

    scanf("%d", &n);

    for (i = 0; i < n; i++) {

        for (j = 0; j < n; j++)

            scanf("%d", &f[i][j]);

    }

    for (i = 1; i <= n; i++) {

        for (j = 1; j <= n; j++) { // 容斥原理得前缀和递推公式

            pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + f[i-1][j-1];

        }

    }

    scanf("%d", &m);

    while (m--) {

        scanf("%d %d %d %d", &a, &b, &c, &d);

        sum = pre[c][d] - pre[c][b-1] - pre[a-1][d] + pre[a-1][b-1];

        if (sum > max) max = sum;

    }

    printf("%d\n", max);

    return 0;

}