HDU-1794 方格填数 （贪心+四分）

题目大意：给一个由自然数构成的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;

}