A94971.排兵布阵 前缀和题解

看没有人用前缀和，就来写一发。

---

前置知识

（地图数组为 $a$，前缀和数组为 $s$）

$$s_{i,j}=a_{i,j}+s_{i-1,j}+s_{i,j-1}-s_{i-1,j-1}$$

以 $(i,j)$ 为左上角、$(k,l)$ 为右下角的区间和为：

$$s_{k,l}-s_{i-1,l}-s_{k,j-1}+s_{i-1,j-1}$$

---

解题思路

遍历所有区间，以 $(i,j)$ 为左上角、$(k,l)$ 为右下角（$i\le k,\ j\le l$），判断区间内所有数的和是否为区间的面积，即 $(k-i+1)\times(l-j+1)$。若是，则区间内全部为 $1$，取最大值。

时间复杂度 $O(n^2m^2)$。

代码

#include <bits/stdc++.h>
using namespace std;
int n,m,ans;
int a[20][20],s[20][20];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
	cin>>n>>m;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            cin>>a[i][j];
            s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            for (int k=i;k<=n;k++){
                for (int l=j;l<=m;l++){
                    if (s[k][l]-s[i-1][l]-s[k][j-1]+s[i-1][j-1]==(k-i+1)*(l-j+1)){
                        ans=max(ans,(k-i+1)*(l-j+1));
                    }
                }
            }
        }
    }
    cout<<ans;
	return 0;
}