题解 | #轰炸区最优选取#

二维前缀和 可与概率论与数理统计的二维概率联系记忆

#include<cstring>
const int N = 1e9 + 7;
using namespace std;
int n,k;
int a[55][55],sum[55][55];
int main(){
    while(cin >> n >> k){
        for(int i = 1;i<=n;i++){
            for(int j =1;j<=n;j++)
            {
            cin >> a[i][j];
            sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
            }
        }
        int maxn=0;
        for(int i =k;i<=n;i++){
            for(int j =k;j<=n;j++){
                maxn=max(maxn,sum[i][j]-sum[i][j-k]-sum[i-k][j]+sum[i-k][j-k]);
            }
        }
        cout<<maxn<<endl;
    }
    
    return 0;
}