轰炸最优区选取
样例
思路:
使用二维前缀和计算0->i,0->j区域的人数,然后再计算k到n围成面积(人数)的大小,取最大值
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 51;
int n,k;
int s[N][N];
int main()
{
while(cin>>n>>k)
{
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>s[i][j];
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
}
int ans=-1;
for(int i=k;i<=n;i++){
for(int j=k;j<=n;j++){
ans=max(ans,s[i][j]+s[i-k][j-k]-s[i][j-k]-s[i-k][j]);
}
}
cout<<ans<<endl;
ans=-1;
memset(s,0,sizeof s);
}
return 0;
}