CCA的矩阵

题目链接：nowcoder 213877

到主站看：https://blog.csdn.net/weixin_43346722/article/details/112135072

题目大意

这是一个 3×3 的锤子能锤到的地方。（反正就是哈曼顿距离小于 3 的都会被锤到）

- - * - -
- * * * -
* * * * *
- * * * -
- - * - -

现在地图上有一些老鼠，问你用大小是 i×i 的锤子锤一次最多能锤到多少个。

思路

看到这个图形，我们可以想到把它摆正。
那我们就把它摆正之后跑前缀和，就可以枚举每个得出打这个点的答案。
然后求最大值，就可以了。

代码

#include<cstdio>
#include<iostream>
#define ll long long

using namespace std;

ll a[2001][2001], q[4001][4001], maxn;
int n, k, tx, ty;

int main () {
    scanf("%d %d",&n, &k);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            scanf("%lld", &a[i][j]);
            q[n + i - j][i + j] = a[i][j];
        }

    for (int i = 1; i <= 2 * n; i++)
        for (int j = 1; j <= 2 * n; j++)
            q[i][j] = q[i][j] + q[i - 1][j] + q[i][j - 1] - q[i - 1][j - 1];

    k = k * 2 - 1;
    for (int i = 1; i <= 2 * n; i++)
        for (int j = 1; j <= 2 * n; j++)
            if ((i + j - n) % 2 == 0) {
                tx = i + k - 1;
                ty = j + k - 1;
                if (tx <= 2 * n && ty <= 2 * n) maxn = max(maxn, q[tx][ty] - q[tx][j - 1] - q[i - 1][ty] + q[i-1][j-1]);
            }

    printf("%lld", maxn);

    return 0;
}