bzoj2241

题解：

暴力枚举锤子大小

然后前缀和判断是否可行

代码：

#include<bits/stdc++.h>
#define N 105  
using namespace std;  
int m,n,tot,a[N][N],s[N][N];  
int pd(int x,int y)
{  
    if (tot%(x*y)) return 0;
    memset(s,0,sizeof(s));  
    for (int i=1;i<=m;i++)  
     for (int j=1;j<=n;j++)
      {  
        s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];  
        if (s[i][j]>a[i][j]) return 0;  
        int t=a[i][j]-s[i][j];  
        if ((i>m-x+1||j>n-y+1)&&t) return 0;  
        if (t){s[i][j]+=t;s[i+x][j]-=t; s[i][j+y]-=t;s[i+x][j+y]+=t;}  
      }  
    return 1;  
}  
int main()
{  
    scanf("%d%d",&m,&n); 
    for (int i=1;i<=m;i++)  
     for (int j=1;j<=n;j++)
      {  
        scanf("%d",&a[i][j]);
        tot+=a[i][j];  
      }  
    int ans=0;  
    for (int i=m;i;i--)
     for (int j=n;j;j--)  
      if (i*j>ans&pd(i,j))ans=i*j;  
    printf("%d
",tot/ans);  
    return 0;  
}