二维前缀和+暴力枚举大小
2026-02-04 15:29:09
发布于:广东
25阅读
0回复
0点赞
题目容易读懂,以下代码大致思路是通过前缀和优化查找,再从小到大暴力枚举每一种面积情况,一但找到,便输出答案,终止程序。
以下为代码:
#include<bits/stdc++.h>
using namespace std;
int n,m,k,sf,v,k1,k2,k3;
string text;
int aa[103][103];
int get_sum(int r,int w,int u,int v){//r为右下角坐标的x,w为y;u为长,v为宽
k1=r-u+1;k2=w-v+1;//左上角坐标
return aa[r][w]-aa[k1-1][w]-aa[r][k2-1]+aa[k1-1][k2-1];
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
cin>>text;
for(int j=1;j<=m;j++){
aa[i][j]=aa[i-1][j]+aa[i][j-1]-aa[i-1][j-1]+text[j-1]-'0';
}
}
int si=n*m;
for(int i=k;i<=si;i++){
for(int u=1;u<=i;u++){
if(i%u==0){
v=i/u;
if(v>m)continue;
for(int r=u;r<=n;r++){
for(int w=v;w<=m;w++){
if(get_sum(r,w,u,v)>=k){
cout<<i;
return 0;
}
}
}
}
}
}
cout<<0;
return 0;
}
这里空空如也





有帮助,赞一个