題目大意：求給定的n(1<=n<=16)個(gè)正整數(shù)邊長(zhǎng)的小正方形（每個(gè)邊長(zhǎng)<=10)能否恰好無重疊拼成一個(gè)邊長(zhǎng)為s的大正方形。
看看數(shù)據(jù)范圍和題目類型，基本也就知道，判斷一下所有小正方形面積之和是否恰為s^2之后，就應(yīng)該搜索了，但是不好確定搜索對(duì)象和順序，是依次將每個(gè)小正方形放入，放置時(shí)一個(gè)一個(gè)位置的試探，還是生成小正方形的放入順序，然后按固定方法放入？
由于n為16，s最大可知是40，相比之下，我們更希望不要過多依賴于s，因此采用后者，并最終確定如下搜索方法：
對(duì)于目標(biāo)大正方形（我們稱作盤子），保證從上到下地放置，即對(duì)于任何一個(gè)狀態(tài)，第 i 列只有前d[i]個(gè)格子已經(jīng)放入正方形，而后面的格子是空的；然后對(duì)于每一種狀態(tài)，都選擇d值最小的一列的第一個(gè)空格作為本次放置正方形的左上頂點(diǎn)，然后枚舉可行的正方形放入并更新受到影響的d值。容易理解這樣的搜索方法是正確的。
還有一個(gè)優(yōu)化不可忽視：邊長(zhǎng)相同的小正方形毫無區(qū)別，因此只需要用c[i](1<=i<=10)記錄邊長(zhǎng)為 i 的小正方形當(dāng)前還有多少個(gè)即可。
為了更大程度的優(yōu)化，我們每一次放置正方形的過程是這樣的（假設(shè)當(dāng)前剩余小正方形中最大最小邊長(zhǎng)為maxl,minl）：
1.找到d[i]值最小的 i＝p（若有多個(gè)取編號(hào)最小的）；
2.找到最大的w使得自第 p 列開始的連續(xù)w列的d值均為d[p]，即求最大的w使d[p]=d[p+1]=...=d[p+w-1]；
3.令 i 從min{l-d[p],maxw,maxl}至minl倒序循環(huán)枚舉將要放置的小正方形邊長(zhǎng)，若c[i]!=0轉(zhuǎn)入4；
4.對(duì)所有p<=j<=p+i-1，令d[j]+=i, c[i]--, 更新maxl,minl, 放置下一個(gè)小正方形，恢復(fù)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;
}