[ SDOI 2011 ] 打地鼠

\(\\\)

\(Description\)

给出一个\(N\times M\)的矩阵，你可以自由确定一个\(R\times C(R,C>0)\)的矩形，使得可以多个用矩形覆盖整个矩阵，覆盖的定义是：

每一个矩形必须完全在矩阵内
每一个矩形所在的矩阵格点权值会\(-1\)
覆盖后整个矩阵所有格点权值全部变为\(0\)

求覆盖的最少所需矩形个数，注意，同一个覆盖所用矩形规格相同。

\(N,M\in [1,100]\)

\(\\\)

\(Solution\)

一看这数据范围还不是乱搞

枚举矩形大小，然后暴力验证，该砸的就砸一锤子。
其实是存在一些类似剪枝的操作的，可以减掉很多无用的枚举：
- 枚举的矩形面积不能整除整个矩阵的权值和。
- 整个矩阵权值和除掉枚举的矩形面积得到的答案没有找到过的优秀。
- 砸一锤子下去发现有的点权不够用（可以枚举砸的左上角）。
因为有\(1\times 1\)的存在，所以不需要考虑无解的情况，暴力模拟轻松过。

\(\\\)

\(Code\)

#include<cmath>

#include<queue>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define N 210

#define R register

#define gc getchar

using namespace std;

int n,m,sum,pos[N][N],tmp[N][N],ans=2000000000;

inline int rd(){

  int x=0; bool f=0; char c=gc();

  while(!isdigit(c)){if(c=='-')f=1;c=gc();}

  while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}

  return f?-x:x;

}

inline void work(int x,int y){

  int res=0;

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

    for(R int j=1;j<=m;++j) tmp[i][j]=pos[i][j];

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

    for(R int j=1,now;j<=m;++j)

      if(tmp[i][j]){

        res+=(now=tmp[i][j]);

        for(R int r=i;r<=i+x-1;++r)

          for(R int c=j;c<=j+y-1;++c)

            if((tmp[r][c]-=now)<0) return;

      }

  ans=min(ans,res);

}

int main(){

  n=rd(); m=rd();

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

    for(R int j=1;j<=m;++j) sum+=(pos[i][j]=rd());

  for(R int i=n;i>=1;--i)

    for(R int j=m;j>=1;--j){

      if(sum%(i*j)==0&&sum/(i*j)<ans) work(i,j);

    }

  printf("%d\n",ans);

  return 0;

}

巴特西

[ SDOI 2011 ] 打地鼠

\(Description\)

\(Solution\)

\(Code\)

最新文章

热门文章