Poj Solution 1020

http://poj.org/problem?id=1020

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
 static int c[]=new int[11];//c[i]��ű߳�Ϊi��С���εĸ���
 static int d[]=new int[41];//d[i]��ʾ��i������С���κ���������
 static int s,n,sum;
 static boolean  ok;

public static void main(String args[])
{
    int t,it,i,tp;
    Scanner sc=new Scanner(System.in);
    t=sc.nextInt();//���Դ�¦
   
    for(it=1;it<=t;it++)//ѭ������ÿһ�β���
    {
        s=sc.nextInt();//�����ӡ������εı߳�
        n=sc.nextInt();//С���εĸ���
        Arrays.fill(c,0);//ÿ�β���ǰ���
         ok=false;
        for(i=1;i<=40;i++) d[i]=1;//
        sum=0;
        for(i=1;i<=n;i++)//���������4ζ���С���εı߳�
        {
            tp=sc.nextInt();
            c[tp]++;//�߳�Ϊtp��С���εĸ������1
            sum+=tp*tp;//ͳ�����
        }
        if(sum!=s*s) ok=false;//�������С�������֮�Ͳ����ڡ����ӡ����
        else {ok=false;dfs(0);}//�����������
       
        if(ok) System.out.println("KHOOOOB!");
        else System.out.println("HUTUTU!");
    }
   }

  public static void dfs(int a)
{
    int i,j,put,p=0;
    boolean f;
    if(a==n) {//�������е�n��С����������ϡ�
       ok=true;
       return;
    }

    //Ѱ��δ��ĺ������С�ĵ�������
    for(i=1,put=41;i<=s;i++){
        if(d[i]< put) {
          put=d[i];//put:�����
          p=i;//p:�����
       }
    }

     //�Ӻ������С�����п�ʼ���Ӵ�С�����������С����
    for(i=10;i>=1;i--)
        if(c[i]>0 && put+i-1<=s && p+i-1<=s)//�����(put,p)���ܷŵ���С����c[i]
        {  
            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;//��ǵ�i������С���κ���������
                
                c[i]--;
                dfs(a+1);
                c[i]++;//��˷
                for(j=p;j<=p+i-1;j++) d[j]-=i;
            }
        }
    }
}