8
1
2016
0

[BZOJ2241] [SDOI2011]打地鼠

模拟一下即可

注意适当的常数优化

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=105,INF=2100000000;

int mp[N][N],mp2[N][N],n,m,ans=INF;

int Test(int r,int c){
int cnt=0;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)mp2[i][j]=mp[i][j];
for(int i=1;i+r-1<=n;i++){
	for(int j=1;j+c-1<=m;j++){
        if(mp2[i][j]){
			int tp=mp2[i][j];
			cnt+=tp;
            for(int k=1;k<=r;k++){
				for(int l=1;l<=c;l++){
                    mp2[i+k-1][j+l-1]-=tp;
                    if(mp2[i+k-1][j+l-1]<0)return INF;
				}
            }
        }
	}
}
for(int i=1;i<=n;i++){
	for(int j=1;j<=m;j++){
		if(mp2[i][j])return INF;
	}
}
return cnt;
}

int main(){
freopen("2241.in","r",stdin);
freopen("2241.out","w",stdout);
scanf("%d %d",&n,&m);
int tx=0;
for(int i=1;i<=n;i++){
	for(int j=1;j<=m;j++){
		scanf("%d",&mp[i][j]);tx+=mp[i][j];
	}
}
for(int r=1;r<=n;r++){
    for(int c=1;c<=m;c++){
		if(tx%(r*c) || tx/(r*c)+1>ans)continue;
        ans=min(ans,Test(r,c));
    }
}
printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 499

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com