当前位置: 代码迷 >> 综合 >> bzoj2241: [SDOI2011]打地鼠
  详细解决方案

bzoj2241: [SDOI2011]打地鼠

热度:22   发布时间:2023-10-29 13:25:52.0

这题的话,先是暴力很容易想到
然后加点判断,可以使复杂度小很多
然后本来还想加个二维树状数组的优化的。。
但由于数据水就没有这个必要了

#include<cstdio>
#include<cstring>
const int MAX=1<<30;
const int N=105;
int a[N][N];
int A[N][N];
int n,m;
int sum=0;
int ans=MAX;
bool check (int x,int y)//锤子有多大 
{for (int u=1;u<=n;u++)for (int i=1;i<=m;i++)a[u][i]=A[u][i];for (int u=1;u<=n;u++){for (int i=1;i<=m;i++){int lalal=a[u][i];if (lalal<0) return false;if (lalal==0) continue;for (int xx=0;xx<x;xx++)for (int yy=0;yy<y;yy++)a[u+xx][i+yy]-=lalal;}}return true;
}
int main()
{scanf("%d%d",&n,&m);for (int u=1;u<=n;u++)for (int i=1;i<=m;i++){scanf("%d",&A[u][i]);sum=sum+A[u][i];}for (int u=1;u<=n;u++)for (int i=1;i<=m;i++){if (sum%(u*i)==0&&sum/(u*i)<ans&&check(u,i))ans=sum/(u*i);}printf("%d\n",ans);return 0;
}