https://codeforces.com/contest/1581/problem/C
题目意思是问在给定的 01 01 01矩阵中，横向长度至少为 5 5 5，纵向长度至少为 4 4 4，把这样一个矩形的四周除了四个顶点其他部分都变成 1 1 1，矩形内部全都变成 0 0 0，问最少需要多少次操作，每次操作可以把一个位置的 1 1 1变成 0 0 0，或者把一个位置的 0 0 0变成 1 1 1

• 题目意思读懂以后，我们应该能够形成一个思路，就是找到所有的这样符合条件的矩形，看需要进行多少次操作，取其中最小的操作数即可，一个矩形需要进行的操作数量应该是他内部矩形的 1 1 1的数量加上边上除了顶点之外的 0 0 0的数量，如何高效操作呢？这里简单介绍一下二维前缀和
  
• 我们使用一个数组 f [ i ] [ j ] f[i][j] f[i][j]存储二维前缀和，表示以 ( 1 , 1 ) (1,1) (1,1)为左上角顶点，以 ( i , j ) (i,j) (i,j)为右下角顶点，的矩形内部所有元素的和（包括边缘），如果我们想求出如上图，以 ( a , b ) (a,b) (a,b)为左上角顶点，以 ( c , d ) (c,d) (c,d)为右下角顶点的矩形内部所有元素之和，怎么求？很简单， f [ c ] [ d ] − f [ c ] [ b − 1 ] − f [ a − 1 ] [ d ] + f [ a − 1 ] [ b − 1 ] f[c][d]-f[c][b-1]-f[a-1][d]+f[a-1][b-1] f[c][d]−f[c][b−1]−f[a−1][d]+f[a−1][b−1]即可，因为左上角的矩形被减掉了两次
• 那么我们怎么求 f [ i ] [ j ] f[i][j] f[i][j]呢？，根据左、右、左上三个位置的 f f f值即可求出，也就是 f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i ] [ j − 1 ] − f [ i − 1 ] [ j − 1 ] + f [ i ] [ j ] f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+f[i][j] f[i][j]=f[i−1][j]+f[i][j−1]−f[i−1][j−1]+f[i][j]，这里同样左上角被加了两次，所以需要减去一个
  明白二维前缀和之后我们再来看这道题就显得很简单了，我们只需要枚举每个矩形，查看所有情况就可以了，注意顶点上的 1 1 1不能算在答案里
• 但是这样看时间复杂度似乎是 O ( n 2 m 2 ) O(n^2m^2) O(n2m2)的，对于 400 400 400的数据范围看起来好像不行，这道题目似乎有点离谱，好像 c f cf cf里面做这种剪枝的不太多，极端情况应该是过不了，但是有一种剪枝方法，我们扩展矩形的方式是固定左上角，根据右下角顶点往右下扩展，先右后下，那么如果当前矩形左边，上下两条边及矩形内部的操作次数已经大于当前答案，那么继续往右也不会得到更优的答案，所以这里 b r e a k break break掉，加这个小小的剪枝可以通过此题

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 500;
char mp[MAXN][MAXN];
int f[MAXN][MAXN];
int cal(int a, int b, int c, int d){
    return f[a][b] + f[c - 1][d - 1] - f[a][d - 1] - f[c - 1][b];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t, n, m;
    cin >> t;
    while(t--){
        cin >> n >> m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin >> mp[i][j];
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + mp[i][j] - '0';
            }
        }
        int ans = 20;
        for(int x=1;x<=n;x++){
            for(int y=1;y<=m;y++){
                for(int i=x+4;i<=n;i++){
                    for(int j=y+3;j<=m;j++){
                        // cout << x << ' ' << y << ' ' << i << ' ' << j << '\n';
                        int jia_l = mp[x][y] + mp[i][y] - '0' - '0';
                        int jia_r = mp[i][j] + mp[x][j] - '0' - '0';
                        int wai = cal(i, j, x, y);
                        int nei = cal(i - 1, j - 1, x + 1, y + 1);
                        int len = i - x - 1;
                        int width = j - y - 1;
                        int r = cal(i, j, x, j) - jia_r;
                        int num = nei + 2 * width + len - (wai - nei - jia_l - jia_r - r);
                        if(ans < num) break;
                        ans = min(ans, nei + 2 * (len + width) - (wai - nei - jia_l - jia_r));
                        // cout << wai << ' ' << nei << ' ' << jia_l << ' ' << jia_r << '\n';
                    }
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

上几道二维前缀和的简单例题
https://www.luogu.com.cn/problem/P1719

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 150;
int f[MAXN][MAXN];
int cal(int a, int b, int c, int d){
    return f[c][d] - f[c][b - 1] - f[a - 1][d] + f[a - 1][b - 1];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin >> f[i][j];
            f[i][j] += f[i][j - 1] + f[i - 1][j] - f[i - 1][j - 1];
        }
    }
    int ans = INT_MIN;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=i;k++){
                for(int q=1;q<=j;q++){
                    ans = max(ans, cal(k, q, i, j));
                }
            }
        }
    }
    cout << ans;
    return 0;
}

http://47.110.135.197/problem.php?id=5182
http://47.110.135.197/problem.php?id=5183