首页 > ACM题库 > HDU-杭电 > HDU 1794 方格填数-递推-[解题报告] C++
2013
12-23

HDU 1794 方格填数-递推-[解题报告] C++

方格填数

问题描述 :

  给你一个N*N的方格,里面都是非负整数(小于32768),我们定义这个方格的总和为:其中的任何一个S*S(1<=S<=N)的子方格中的数字的总和。由于中间有K(0<=K<=N*N)个单位方格中的数字是0,因此现在给定你M(K<=M&&M<=10000)个正整数(小于32768),你可以从中选择K个,来填入原来的N*N的值为0的单位方格中,从而最大化的增加我们定义的方格的总和。

输入:

  这里有T组测试数据,第一行输入T,T<=100。对于测试数据,先输入一个N(N<=30),然后输入一个N*N的矩阵,中间含0的元素,然后给定一个M,后一行输入M个正整数。

输出:

  对于每组测试数据,输出能够最大的增加的值。

样例输入:

1
3
1 2 3
4 0 2
0 2 7
4
2 9 4 7

样例输出:

75

方格填数

 

求出每个为0的方格在多少个s*s的中

当n==30时达到2000多,和超int

 

 

 

 

 

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int map[31][31],a[10010];
struct op
{
	int num,count;
}p[31][31];
struct ed
{
	int x,y,cnt;
}e[1000];
int cmp(const void *a,const void *b)
{
	return *(int *)b-*(int *)a;
}
int amp(const void *a,const void *b)
{
	struct ed *c,*d;
	c=(ed *)a;
	d=(ed *)b;
	return d->cnt-c->cnt;
}
int MAX(int a,int b)
{
	if(a>b)return a;
	return b;
}
int main()
{
	int i,n,j,k,t,x,y,temp,m;
	__int64 sum;
	scanf("%d",&t);
	while(t--)
	{
		sum=0;
		scanf("%d",&n);
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				scanf("%d",&map[i][j]);
				p[i][j].num=n-MAX(i,j);//以[i][j]为左上角的方格的个数
				p[i][j].count=p[i][j].num;//[i][j]在所属多少个方格
			}
		}
		scanf("%d",&m);
		for(i=0;i<m;i++)
			scanf("%d",&a[i]);
		qsort(a,m,sizeof(a[0]),cmp);
		for(i=0;i<n-1;i++)
		{
			for(j=0;j<n-1;j++)
			{
				x=i+1;y=j+1;temp=1;
				while(x<n&&y<n)//以[i][j]为左上角,[x][y]右下角的方格
				{
					p[x][y].count+=p[i][j].num-temp;
					k=x-1;
					while(k>=i)//i到x-1这一列的
					{
						p[k][y].count+=p[i][j].num-temp;
						k--;
					}
					k=y-1;
					while(k>=j)//j到y-1这行的
					{
						p[x][k].count+=p[i][j].num-temp;
						k--;
					}
					x++;y++;//方格的边长增加1
					temp++;//方格最右边和最下边被覆盖的次数就减就比上一个方格的少1
				}
			}
		}
		k=0;
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
				if(map[i][j]==0)
				{
					e[k].x=i;
					e[k].y=j;
					e[k++].cnt=p[i][j].count;
				}
		}
		qsort(e,k,sizeof(e[0]),amp);//按所属方格数的多少排序
		for(i=0;i<k;i++)
		{
			x=e[i].x;
			y=e[i].y;
			sum+=p[x][y].count*a[i];
		}
		printf("%I64d\n",sum);			
	}
	return 0;
}

 

解题报告转自:http://blog.csdn.net/aixiaoling1314/article/details/8889132


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。