[bzoj2241]打地鼠

先考虑如何判定一个r*c的矩阵是否符合条件，容易发现左上角的点无法被别的矩阵砸到，要求左上角r*c的矩阵中不能超过最左上角的元素，之后同理不断枚举最上&最左的非0点，可以用差分来优化，复杂度为$o(n^{4})$（n和m同阶）
（然后加上一些整除、倒序枚举的剪枝就可以过了）
正解是这样的，枚举1*c的最大矩阵，枚举r*1的最大矩阵，r*c的矩阵即为答案（这个用差分维护）
为了证明这个的正确性，分为两部分考虑：
1.必要性，即r*c的矩阵合法可以推出1*c和r*1的矩阵合法，显然成立（用c次r*1的矩阵/r次c*1的矩阵即可）
2.充分性，即1*c和r*1的矩阵合法可以推出r*c的矩阵合法，考虑对于当前的左上角，竖着敲了x次，说明每一列都超过了x，那么必然会导致每一行都敲至少x，也就是对r*c的矩阵敲了x次
问题即得证，那么最终正解的复杂度为$o(n^{3})$（n和m同阶）

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 int n,m,s,ans,a[105][105],b[105][105];

 4 bool pd(int r,int c){

 5     memcpy(b,a,sizeof(a));

 6     for(int i=1;i<=n;i++)

 7         for(int j=1;j<=m;j++)

 8             if (b[i][j]){

 9                 if ((i+r-1>n)||(j+c-1>m))return 0;

10                 int p=b[i][j];

11                 for(int x=i;x<i+r;x++)

12                     for(int y=j;y<j+c;y++)

13                         if ((b[x][y]-=p)<0)return 0;

14             }

15     return 1;

16 }

17 int main(){

18     scanf("%d%d",&n,&m);

19     for(int i=1;i<=n;i++)

20         for(int j=1;j<=m;j++){

21             scanf("%d",&a[i][j]);

22             s+=a[i][j];

23         }

24     for(int i=n;i;i--)

25         for(int j=m;j;j--)

26             if ((s%(i*j)==0)&&(i*j>ans)&&(pd(i,j)))ans=i*j;

27     printf("%d",s/ans);

28 }

巴特西

[bzoj2241]打地鼠

最新文章

热门文章