題目大意:求給定的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<=&& 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;
}