题目大意：求给定的n(1<=n<=16)个正整数边长的小正方形（每个边长<=10)能否恰好无重叠拼成一个边长为s的大正方形。
看看数据范围和题目类型，基本也就知道，判断一下所有小正方形面积之和是否恰为s^2之后，就应该搜索了，但是不好确定搜索对象和顺序，是依次将每个小正方形放入，放置时一个一个位置的试探，还是生成小正方形的放入顺序，然后按固定方法放入？
由于n为16，s最大可知是40，相比之下，我们更希望不要过多依赖于s，因此采用后者，并最终确定如下搜索方法：
对于目标大正方形（我们称作盘子），保证从上到下地放置，即对于任何一个状态，第 i 列只有前d[i]个格子已经放入正方形，而后面的格子是空的；然后对于每一种状态，都选择d值最小的一列的第一个空格作为本次放置正方形的左上顶点，然后枚举可行的正方形放入并更新受到影响的d值。容易理解这样的搜索方法是正确的。
还有一个优化不可忽视：边长相同的小正方形毫无区别，因此只需要用c[i](1<=i<=10)记录边长为 i 的小正方形当前还有多少个即可。
为了更大程度的优化，我们每一次放置正方形的过程是这样的（假设当前剩余小正方形中最大最小边长为maxl,minl）：
1.找到d[i]值最小的 i＝p（若有多个取编号最小的）；
2.找到最大的w使得自第 p 列开始的连续w列的d值均为d[p]，即求最大的w使d[p]=d[p+1]=...=d[p+w-1]；
3.令 i 从min{l-d[p],maxw,maxl}至minl倒序循环枚举将要放置的小正方形边长，若c[i]!=0转入4；
4.对所有p<=j<=p+i-1，令d[j]+=i, c[i]--, 更新maxl,minl, 放置下一个小正方形，恢复d[i],c[i],maxl,minl值，返回3。
代码如下：
#include<iostream>
using namespace std;
int c[11],d[41],s,n,sum;
bool ok;
void dfs(int a)
{
int i,j,put,p;
bool f;
if(a==n) {ok=true;exit;}
for(i=1,put=41;i<=s;i++)
if(d[i]<put) {put=d[i];p=i;}
for(i=10;i>=1;i--)
if(c[i]>0 && put+i-1<=s && p+i-1<=s)
{
for(j=p,f=true;j<=p+i-1;j++)
if(d[j]>put) {f=false;break;}
if(f)
{
for(j=p;j<=p+i-1;j++) d[j]+=i;
c[i]--;
dfs(a+1);
c[i]++;
for(j=p;j<=p+i-1;j++) d[j]-=i;
}
}
}
int main()
{
int t,it,i,tp;
cin>>t;
for(it=1;it<=t;it++)
{
cin>>s>>n;
memset(c,0,sizeof(c));
for(i=1;i<=40;i++) d[i]=1;
sum=0;
for(i=1;i<=n;i++)
{
cin>>tp;
c[tp]++;
sum+=tp*tp;
}
if(sum!=s*s) ok=false;
else {ok=false;dfs(0);}
if(ok) cout<<"KHOOOOB!"<<endl;
else cout<<"HUTUTU!"<<endl;
}
system("pause");
return 0;
}