模拟一下即可
注意适当的常数优化
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=105,INF=2100000000;
int mp[N][N],mp2[N][N],n,m,ans=INF;
int Test(int r,int c){
int cnt=0;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)mp2[i][j]=mp[i][j];
for(int i=1;i+r-1<=n;i++){
for(int j=1;j+c-1<=m;j++){
if(mp2[i][j]){
int tp=mp2[i][j];
cnt+=tp;
for(int k=1;k<=r;k++){
for(int l=1;l<=c;l++){
mp2[i+k-1][j+l-1]-=tp;
if(mp2[i+k-1][j+l-1]<0)return INF;
}
}
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp2[i][j])return INF;
}
}
return cnt;
}
int main(){
freopen("2241.in","r",stdin);
freopen("2241.out","w",stdout);
scanf("%d %d",&n,&m);
int tx=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&mp[i][j]);tx+=mp[i][j];
}
}
for(int r=1;r<=n;r++){
for(int c=1;c<=m;c++){
if(tx%(r*c) || tx/(r*c)+1>ans)continue;
ans=min(ans,Test(r,c));
}
}
printf("%d\n",ans);
return 0;
}
评论 (0)
