HDU-1794 方格填数 (贪心+四分)

时间:2024-05-30 16:03:38

题目大意:给一个由自然数构成的nxn方阵,其中有k个元素为0,现在要从给出的m个元素中挑出k个填入矩阵,是和的增量最大。和定义为所有子方阵上的元素之和。

题目分析:对于尺寸固定的方阵,计算和的时候每个元素做加数的次数是可以求出的,只需将最大的数放入做加数次数最多的位置,以此类推,便得到答案。要预先处理出每个位置上的元素做加数的次数,我用的四分。

代码如下:

# include<cstdio>
# include<cstring>
# include<iostream>
# include<algorithm>
using namespace std;
# define LL long long int n,m,a[35][35][35];
int b[1000],w[10005]; void dfs(int id,int x,int y,int r,int c)
{
if(r==1||c==1){
if(r==1&&c==1){
++a[id][x][y];
return ;
}else{
if(r==1){
dfs(id,x,y,r,c/2);
dfs(id,x,y+c/2,r,c-c/2);
}else if(c==1){
dfs(id,x,y,r/2,c);
dfs(id,x+r/2,y,r-r/2,c);
}
}
}else{
dfs(id,x,y,r/2,c/2);
dfs(id,x,y+c/2,r/2,c-c/2);
dfs(id,x+r/2,y,r-r/2,c/2);
dfs(id,x+r/2,y+c/2,r-r/2,c-c/2);
}
} void init()
{
memset(a,0,sizeof(a));
for(int id=1;id<=30;++id)
for(int l=1;l<=id;++l)
for(int i=0;i+l-1<id;++i)
for(int j=0;j+l-1<id;++j)
dfs(id,i,j,l,l);
} int main()
{
init();
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int k=0,x;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j){
scanf("%d",&x);
if(!x) w[k++]=a[n][i][j];
}
scanf("%d",&m);
for(int i=0;i<m;++i)
scanf("%d",b+i);
sort(b,b+m);
sort(w,w+k);
LL ans=0;
for(int i=1;i<=k;++i)
ans+=(LL)w[k-i]*(LL)b[m-i];
printf("%lld\n",ans);
}
return 0;
}