> 10 
> 21 16 5 7 2 4 8 9 4 2 3 2 4 2 9 6 4 4 
> 28 16 10 10 7 3 5 9 10 3 8 5 7 7 5 7 1 7 
> 13 11 1 2 2 8 1 2 3 7 1 4 4 
> 23 16 1 7 5 8 5 10 9 2 1 4 2 6 3 1 8 7 
> 26 16 3 7 10 9 8 3 1 9 6 6 8 2 10 1 5 4 
> 21 16 6 5 10 4 2 3 4 7 7 2 3 3 1 1 7 8 
> 18 14 2 6 3 1 2 3 9 9 4 5 7 2 1 2 
> 15 12 3 1 3 1 8 1 5 1 6 2 6 3 
> 22 15 2 6 8 5 4 7 9 9 4 5 4 3 6 3 4 
> 22 14 4 1 6 7 9 1 7 3 10 8 1 6 5 4 
> 
> HUTUTU! 
> HUTUTU! 
> HUTUTU! 
> KHOOOOB! 
> KHOOOOB! 
> KHOOOOB! 
> KHOOOOB! 
> HUTUTU! 
> HUTUTU! 
> KHOOOOB! 
> 
> 基本思路就是从左到右,从上往下，枚举每个小正方形放进去。
> #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;
> }


代码确实不错。。感觉并不是不剪枝。。
for(i=10;i>=1;i--)
	if(c[i]>0 && put+i-1<=s && p+i-1<=s)
这里就直接吧相同的给处理掉了。。

感觉巧妙之处就是把相同的蛋糕放在一起计数了。。否则还得排序。。然后在处理的时候比较来剪掉相同的。。

在网上找到一个更方便读的。。还有注释。。搞了一上午。。算明白了。。

尊重作者：http://cool8511.blog.hexun.com/32069650_d.html

#include <stdio.h>
#include <memory.h>
int cakeside,piecenum,pieces[11];
//fillednum stand for the nums had filled
bool fill(int fillednum,int* used)
{
    //如果已填的个数等于需求的蛋糕个数则表示刚好
    if(fillednum==piecenum)
        return true;
    int i,j,minusedrow=41,nowcol=0;
    //寻找未填的行数最小的那列
    for(i=1;i<=cakeside;i++)
    {
        if(used[i]<minusedrow)
        {
            minusedrow = used[i];
            nowcol = i;
        }
    }
    //从行数最小的那列开始，从大到小搜索能填入的蛋糕
    for(i=10;i>0;--i)
    {
        if(pieces[i]>0 && i+minusedrow<=cakeside+1 && i+nowcol<=cakeside+1)
        {
            bool flag=true;
            //判断连续的区域是否能放下当前蛋糕
            for(j=nowcol;j<nowcol+i;j++)
            {
                if(used[j]>minusedrow)
                {
                    flag=false;
                    break;
                }
            }
            if(flag)
            {
                //能放下则更新蛋糕所在的列的已填行数
                for(j=nowcol;j<nowcol+i;j++)
                    used[j] += i;
                //当前大小蛋糕数减一
                pieces[i]--;
                //继续切下一块蛋糕
                if(fill(fillednum+1,used))
                    return true;
                //到这说明上面方案不可行，回溯，不能切当前大小的蛋糕
                pieces[i]++;
                for(j=nowcol;j<nowcol+i;j++)
                    used[j] -= i;
            }
        }
    }
    return false;
}
int main()
{
    int ncase,i,j;
    scanf("%d",&ncase);
    while(ncase>0)
    {
        --ncase;
        int sum=0;
        int pieceside;
        scanf("%d %d",&cakeside,&piecenum);
        memset(pieces,0,sizeof(pieces));
        //记录各不同大小的蛋糕个数，大小范围在1-10之间
        for(i=0;i<piecenum;++i)
        {
            scanf("%d",&pieceside);
            //大小为pieceside的个数
            pieces[pieceside]++;
            sum += pieceside*pieceside;
        }
        if(sum!=cakeside*cakeside)
        {
            printf("HUTUTU!\n");
            continue;
        }
        bool IsWaste=true;
        //used[i]记录的是第i列还没填的那行
        int used[41];
        for(i=1;i<=40;i++) used[i]=1;
        //fill表示从第几块蛋糕开始填是否能刚好填满所有蛋糕
        IsWaste = !fill(0,used);
        if(IsWaste)
            printf("HUTUTU!\n");
        else
            printf("KHOOOOB!\n");

    }
    return 0;
}

PS：感觉在网页看代码太乱。。ctrl+v到notepad2看着舒服。。嘿嘿。。

• 想问问41是什么...最多是边长16的正方形...为什么不是17 (16) hust_oneDianer 2012-02-03 15:52:49
• Re:数据太弱,暴力搜索不剪枝AC！ (26) LoiteringLeo 2012-12-07 23:51:39