链接：

来源：牛客网

题目描述

矩阵 M 包含 R 行 C 列，第 i 行第 j 列的值为 M

_i,

_j。

请寻找一个子矩阵，使得这个子矩阵的和最大，且满足以下三个条件：

子矩阵的行数不能超过 X 行。

子矩阵的列数不能超过 Y 列。

子矩阵中 0 的个数不能超过 Z 个。

请输出满足以上条件的最大子矩阵和。

输入描述:

第一行输入五个整数 R，C，X，Y，Z。

接下来 N 行，每行输入 M 个整数，第 i 行第 j 列的整数表示 M

_i,

_j。

1 ≤ R,C ≤ 500.

1 ≤ X ≤ R. 1 ≤ Y ≤ C. 1 ≤ Z ≤ R x C. -10

⁹ 

≤  M

_i,j  

≤ 10

⁹

输出描述:

输出满足以上条件的最大子矩阵和。

示例1

输入

5 5 3 3 40 0 10 0 03 4 0 2 3-1 3 0 -8 30 0 32 -9 33 0 45 3 0

输出

82

示例2

输入

2 2 2 2 2-1 -1-1 -1

输出

0 题意 ： 在一个大的矩阵中寻找一个小的矩阵，但是行列是有要求的。 思路分析： 枚举行的起点和终点，复杂度是 O(n^2) ， 通过预处理前缀和，可以得到此时的一行的数，再O（n）的用单调队列搞一下即可 代码示例 ： （WA 了 ， 还在调试中 ）

#include 
          
           using namespace std;#define ll long longconst ll maxn = 1e6+5;typedef pair
           
            pa;ll n, m;ll x, y, z;ll mp[505][505], sum[505][505], cnt[505][505], ze[505][505];ll f[505], f2[505];pa que[2005];int main() {    //freopen("in.txt", "r", stdin);    //freopen("out.txt", "w", stdout);        cin >> n >> m >> x >> y >> z;    for(ll i = 1; i <= n; i++){        for(ll j = 1; j <= m; j++){            scanf("%lld", &mp[i][j]);            if (mp[i][j] == 0) ze[i][j] = 1;        }    }        for(ll i = 1; i <= n; i++){        for(ll j = 1; j <= m; j++){            cnt[i][j] = cnt[i-1][j]+ze[i][j];            sum[i][j] = sum[i-1][j]+mp[i][j];        }    }     ll ans = 0;    for(ll i = 1; i <= n; i++){        for(ll j = i; j <= n; j++){            if (j-i+1 > x) break;            ll l=0, r = 0 ;            memset(que, 0, sizeof(que));            memset(f, 0, sizeof(f));            memset(f2, 0, sizeof(f2));            for(ll k = 1; k <= m; k++){                ll num = sum[j][k]-sum[i-1][k];                ll zero = cnt[j][k]-cnt[i-1][k];                f[k] = f[k-1]+num;                                f2[k] = f2[k-1]+zero;                while (l < r && que[r-1].first > f[k]){                    r--;                }                que[r++] = make_pair(f[k], k);                                while(l < r && k-que[l].second+1 > y) {l++; }                while(l < r && f2[k]-f2[que[l].second-1] > z) {l++; }                if (l< r) ans = max(ans, f[k]-f[que[l].second-1]);                                //prllf("%lld %lld %lld %lld  l = %lld r = %lld \n", i, j, k, ans, l, r);            }        }    }    printf("%lld\n", ans);    return 0;}