pku1020 Anniversary Cake


#include<stdio.h>
#include<string.h>

int size,n,cake[11],col[41];
bool exist;

void dfs(int depth)
{
    if(depth==n)
    {
        exist=true;
        return;
    }

    int startX=41,startY,len=0;        //startX,stratY记录大正方形最上面未利用的空白间隙的位置

    for(int i=1;i<=size;i++)        
    {                                
        if(startX>col[i])
        {
            startX=col[i];
            startY=i;
        }
    }
    for(int i=startY;i<=size;i++)    //len记录间隙空白间隙的横向宽度，下面startX+边长<=size为纵向约束

    {
        if(col[i]>startX) break;
        len++;
    }

    for(int i=10;i>0;i--)    
    {
        if(cake[i]>0&&startX+i<=size&&i<=len)    //存在某种小正方形能容纳在最上面的空白间隙中    

        {
            for(int j=i-1;j>=0;j--) col[startY+j]+=i;
            cake[i]--;
            dfs(depth+1);
            if(!exist)            
            {
                cake[i]++;
                for(int j=i-1;j>=0;j--) col[startY+j]-=i;
            }
        }
    }
}

int main()
{
    int cases;
    scanf("%d",&cases);
    while(cases--)
    {
        scanf("%d%d",&size,&n);     //用size个竖条来模拟大正方形

        memset(cake,0,sizeof(cake));        
        memset(col,0,sizeof(col));
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            int kind;
            scanf("%d",&kind);
            sum+=kind*kind;
            cake[kind]++;        //以边长分类记录小正方形

        }
        if(size*size!=sum)    
        {
            printf("HUTUTU!\n");
        }
        else
        {
            exist=false;
            dfs(0);
            if(exist) printf("KHOOOOB!\n");
            else printf("HUTUTU!\n");
        }
    }
    return 0;
}