poj1020--Anniversary Cake题解

原题：http://acm.pku.edu.cn/JudgeOnline/problem?id=1020

题目要求我们检测是否能将给定的多个小正方形拼成一个完整的大的正方形。

采用搜索遍历的方法：

拼凑的方法类似于俄罗斯方块游戏，不同的是每次拼凑的时候必须先找到高度最低的那一列拼凑，如果某一个小正方形不成功的话，则回溯。

#include<iostream>
using namespace std;

const int maxSize = 40;
const int maxOfCakes = 10;
int cakeSize,npieces;
int cakes[maxOfCakes+1],len[maxSize+1];

bool Check(int usedNum)
{
	if(usedNum==npieces)
		return true;

	int min = maxSize,ind = 0;
	for(int col=1;col<=cakeSize;col++)	//找到高度最低的那一列
	{
		if(min>len[col])
		{
			min = len[col];
			ind = col;
		}
	}

	for(int cs=1;cs<=maxOfCakes;cs++)
	{
		if(cakes[cs] && len[ind]+cs<=cakeSize)
		{
			int width = 0;
			for(int i=ind;i<=cakeSize;i++)
			{
				if(len[i]==len[ind])
					width++;
				else
					break;
			}

			if(width>=cs)
			{
				cakes[cs]--;
				for(int i=ind;i<ind+cs;i++)
					len[i] += cs;
				if(Check(usedNum+1))
					return true;
				for(int i=ind;i<ind+cs;i++)
					len[i] -= cs;
				cakes[cs]++;
			}
		}
	}

	return false;
}

int main()
{
	int testNum;
	cin>>testNum;

	int side,sum;
	for(int i=0;i<testNum;i++)
	{
		for(int j=0;j<=maxSize;j++)
			len[j] = 0;
		for(int j=0;j<=maxOfCakes;j++)
			cakes[j] = 0;

		cin>>cakeSize>>npieces;
		sum = 0;
		for(int j=0;j<npieces;j++)
		{
			cin>>side;
			sum += side*side;
			cakes[side]++;
		}
		if(cakeSize*cakeSize==sum && Check(0))
		{
			cout<<"KHOOOOB!"<<endl;
		}
		else
		{
			cout<<"HUTUTU!"<<endl;
		}
	}

	return 0;
}