本文共 2226 字，大约阅读时间需要 7 分钟。

题意：有一个大小为s*s的蛋糕，现给出n(1<=n<=16)个正方形的小蛋糕，小蛋糕的边长范围是1到10，问大蛋糕能否恰好由小蛋糕组合而成。简言之，一个大正方形能否恰由给出的小正方形组成。

  算法：dfs，从上到下，从左到右，从大蛋糕到小蛋糕依次尝试/枚举  最简单的思路是先按蛋糕的尺寸逆序排序小蛋糕，然后枚举每个小蛋糕，但是TLE。原因很简单，假如第i次尝试的是j个蛋糕，如果失败了，会尝试第j+1个蛋糕，但是假如第j+1个蛋糕的尺寸和第j个蛋糕的尺寸相同，同样会失败，此处需要剪枝。 后来，按照蛋糕的尺寸从大到小进行枚举，如果尺寸为i的蛋糕枚举失败了，下一次尝试的是i-1的蛋糕，这样就避免了上述存在重复枚举的问题。 那么，怎样记录大蛋糕哪些位置已放入了小蛋糕呢？  开始使用数组row[i]=j表示，即第i行的前j列都已放入了小蛋糕，但是这种做法是错误的，具体见图(第4行无法正确表示)。 然后使用数据col[i]=j表示，即第i列的前j行都已放入了小蛋糕，因为是从上到下从左到右放小蛋糕，即行优先放，如果第i列的第j行还未放，那么该行第j+1列是不会放的 。

#include 
   
    #include 
    
     #include 
     
      using namespace std;int piece[20];		// piece[i]=j： i*i的piece有j个 int col[50];		// col[i] = j： 第i列的前j行已放入piece bool ans;			 // 从第l列开始，放入/拿走w*w的piece ，k=1时放入，k=-1是拿走 void update(int l,int w,int k){	for (int i=l; i<=l+w-1; i++)	{		col[i] = col[i] + k * w;	} }// curr_n：当前已放入piece的个数 void dfs(int curr_n,int s,int n){	if (curr_n == n)	{		if (col[s] == s)		{			ans = true;			exit;		}		return;	}		// 找出当前可以放piece的位置(pre_min_row,min_col) 	int pre_min_row = 50;	int min_col;	for (int i=1; i<=s; i++)	{		if (col[i] < pre_min_row)		{			pre_min_row = col[i];			min_col = i;		}	}		// 枚举每一个piece 	for (int i=10; i>0; i--)	{		// 如果不存在i*i的piece或是已得到答案 		if (piece[i]<=0 || ans)		{			continue;		}		// 如果超出列宽或行宽 		if (pre_min_row+i > s || min_col+i-1 > s)		{			continue;		}		// 计算从 (pre_min_row,min_col) 开始的空白宽度wide 		int wide = 0;		for (int j=min_col; j<=min_col+i-1; j++)		{				// 连续的空间 			if (col[j] > col[min_col])			{				break;			}				wide++;		}		// 如果可以放下i*i的piece 		if (wide >= i)		{ 			piece[i]--;			update(min_col,i,1);			dfs(curr_n+1,s,n);			piece[i]++;			update(min_col,i,-1);		}	}}int main(){	int t;		// the number of test cases	int s;		// the side of the cake	int n;		// the number of the cake pieces	cin >> t;	for (int i=0; i
      
       > s;		cin >> n;		int sum_piece = 0;		int piece_size;		int gt_half_num = 0; 		// 尺寸大于s/2的piece个数，如果个数大于等于2，那么无法放下 		for (int j=0; j
       
        > piece_size;			piece[piece_size]++;			sum_piece += piece_size*piece_size;			if (piece_size > s/2)			{				gt_half_num++;			}		}		if (sum_piece != s*s || gt_half_num >= 2)		{			cout << "HUTUTU!" << endl;			continue;		}		ans = false;		dfs(0,s,n);		ans? cout << "KHOOOOB!" << endl : cout << "HUTUTU!" << endl;	}}