首页 > ACM题库 > HDU-杭电 > hdu 2442 Bricks-线性结构-[解题报告]C++
2014
01-26

hdu 2442 Bricks-线性结构-[解题报告]C++

Bricks

问题描述 :

Little White bought a new house recently. She doesn’t like the design of the floor anyway, so she decides to decorate the floor. Now she has bricks of the 5 shapes below, all with an infinite amount.

Bricks cannot overlap each other, and you cannot rotate them to fit in the "holes".

Now, please tell Little White how many units can she cover using these bricks.

输入:

For every test case, you are given two integers n and m indicating the floor is an n*m rectangle

consisting of n*m 1*1 grids.(1<=n<=100,1<=m<=6)

Proceed to the end of file.

输出:

For every test case, you are given two integers n and m indicating the floor is an n*m rectangle

consisting of n*m 1*1 grids.(1<=n<=100,1<=m<=6)

Proceed to the end of file.

样例输入:

1 4
2 3
3 2
4 4 

样例输出:

0
4
4
12 

#include <iostream>
#include <queue>
#include <stdio.h>
using namespace std;

int main(int argc, const char * argv[])
{
	int cas,n,m,t;
	priority_queue<int,vector<int>,greater<int> >Q0;
	priority_queue<int,vector<int>,less<int> >Q1;
	int tmp_arr[2001],arr[2001];
	cin >> cas;
	while (cas--) {
		cin >> m >> n;
		for (int j=0; j<n; j++) {
			cin>>t;
			Q0.push(t);
		}
		while (--m) {
			int i=0;
			for (int j=0; j<n; j++)
				cin>>arr[j];
			while (!Q0.empty()) {
				tmp_arr[i++]=Q0.top();
				Q0.pop();
			}
			for (int j=0; j<n; j++)
				Q1.push(tmp_arr[j]+arr[0]);
			for (int j=1; j<n; j++) {
				for (int k=0; k<n; k++) {
					if (tmp_arr[k]+arr[j]>=Q1.top())
						break;
					Q1.push(tmp_arr[k]+arr[j]);
				}
				for (int j=Q1.size(); j>n; j--)
					Q1.pop();
			}

			while (!Q1.empty()) {
				Q0.push(Q1.top());
				Q1.pop();
			}
		}
		for (int j=0; j<n; j++) {
			j&&putchar(' ');
			cout<<Q0.top();
			Q0.pop();
		}
		puts("");
	}
	return 0;
}

通过带入下个数组,刷新最小的n个元素,维护堆的大小为n!

其中的诡异代码是在刷新过程中要一直保持队列大小为n,这样子就可以通过tmp_arr[k]+arr[j]>=Q1.top() 剪枝,因为当Q1.top()越小,剪枝越明显!!如果不理Q1大小,而在最后刷新完之后,再恢复,那么中间的剪枝就没用了!!!!我sb了。。

解题转自:http://blog.csdn.net/songrgg/article/details/8138359


  1. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  2. 样例输出和程序输出不吻合,修改一下样例输出吧。我用的是VC编译器,会提示我的i和j变量重复定义