【SDOI2011】打地鼠

题解 优雅的暴力

由于我常用的OJ炸了，我暂时先把Luogu上的题面放上来
LuoguP2484

看完题目回来了吧。
一开始看题的时候觉得这题很简单，但是某ghbdalao写完这题M掉了，我眉头一皱觉得这并不好玩。

那么先把题目简化为OIer友好的格式吧。
简单来说，给出一个矩阵，每次操作可以也只能将一个固定区间内的所有数减1，求最小操作的次数。

首先可以发现一个性质，就是一旦确定了区间的长和宽，我们操作的次序是无关紧要的。因为左上角的点能且仅能被左上角开始的操作覆盖，所以在枚举是否可行的时候，我们实际上只需要循环减去就可以了，代码其实可以像这样

bool judge(int r,int c){
    int temp[maxn][maxn];memcpy(temp,val,sizeof(val));//现开一个数组便于判断
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (temp[i][j]){//因为我从左上枚举，所以枚举到一个点时我必须打他
                if (i+r<=n+1&&j+c<=m+1){
                    int num=temp[i][j];
                    for (int row=0;row<r;row++){
                        for (int col=0;col<c;col++){
                            temp[i+row][j+col]-=num;//循环减去
                            if (temp[i+row][j+col]<0) return 0;//倘若不合法就失败
                        }
                    }
                }
            }
        }
    }            
    return 1;
}

然后我们就可以枚举长和宽写代码了。
某ghbdalao想出这个后写了个暴力判断 60

为什么是60呢？我们看，每一次判断是否可行我们复杂度是O(n^2*m^2)，枚举长宽复杂度是O(nm)
乘起来之后复杂度变为O(n^3*m^3)，对于n,m<=100的数据自然会过不了的。

过不了怎么办？
那就剪枝，优雅地爆搜
可行性剪枝
题目中明确的给出我必须一次打掉r*c，不妨记录总数，一旦我当前枚举的r*c不可以被sum整除，那么便一定不合法，可以直接跳过。
最优性剪枝
我在枚举过程中是要记录值的，倘若我当前的r*c小于等于我枚举过且更新成功值的r*c，那么一定没必要枚举并判断他。

经过这两个剪枝，在Luogu上便可以AC了

AC代码

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=110;
int val[maxn][maxn];
int n,m,sum,ans;
int r,c;
void read(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            scanf("%d",&val[i][j]);
            sum+=val[i][j];
        }
    }
}
bool legal(int r,int c){
    if (r<0||r>n) return 0;
    if (c<0||c>n) return 0;
    return 1;
}
bool judge(int r,int c){
    int temp[maxn][maxn];memcpy(temp,val,sizeof(val));
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (temp[i][j]){
                if (i+r<=n+1&&j+c<=m+1){
                    int num=temp[i][j];
                    for (int row=0;row<r;row++){
                        for (int col=0;col<c;col++){
                            temp[i+row][j+col]-=num;
                            if (temp[i+row][j+col]<0) return 0;
                        }
                    }
                }
            }
        }
    }            
    return 1;
}
int main(){
    read();
    for (int r=n;r>=1;r--){
        for (int c=m;c>=1;c--){
            if (sum%(r*c)||r*c<=ans) continue;
            if (judge(r,c)) ans=r*c;
        }
    }
//    printf("%d %d\n",sum,ans);
    printf("%d",sum/ans);
}

几个简单却行之有效的优化

1.我们看到，在判断时枚举实在是太暴力了，因此可以用前缀和优化。
2.在最优性剪枝中，因为我们是倒序枚举的，所以我们可以把可行(即满足sum%r*c==0)的解全部保存，按面积排序在判断
加上这两个优化后ghb8ms水过这道题。