pku 1020

2009年8月7日

题目链接：PKU 1020 Anniversary Cake
 
分类：DFS应用

题目分析与算法原型：
         题目大意就是给你些整边长小正方形问你能否拼成一个给定的整边长的大正方形。看数据范围和题目类型，可以知道，先判断一下所有小正方形面积之和是否恰为s^2之后，就应该dfs了.
        大致做法是：按从左到右从上到下的顺序来放小正方形，先将大正方形看成一个二维数组，定义一个数组hang[],hang[i]表示第i列前面的hang[i]行已经被占用了，然后先找到hang[i]最小的那个以它作为下一个放正方形的左上顶点，接着每次从大到小枚举所剩的正方形看能否放入（可以直接从10到1枚举小正方形的边长），若能放入，再接着DFS.......        

Code:

 1#include<stdio.h>
 2#include<string.h>
 3int t,s,n,hang[42],c[11];
 4bool dfs(int num)
 5{
 6    int i,j,minpos=41,lie;
 7    if(num==n)return true;
 8    for(i=1;i<=s;i++)
 9        if(hang[i]<minpos)
10        {
11            minpos=hang[i];
12            lie=i;
13        }
14    for(i=10;i>=1;i--)
15        if(c[i]&&minpos+i<=s&&lie+i-1<=s)
16        {
17            for(j=lie;j<=lie+i-1;j++)if(hang[j]>minpos)break;
18            if(j>lie+i-1)
19            {
20                c[i]--;
21                for(j=lie;j<=lie+i-1;j++)hang[j]+=i;
22                if(dfs(num+1))return true;
23                for(j=lie;j<=lie+i-1;j++)hang[j]-=i;
24                c[i]++;
25            }
26        }
27        return false;
28}
29int main()
30{
31    int i,sum,size;
32    scanf("%d",&t);
33    while(t--)
34    {
35        scanf("%d%d",&s,&n);
36        memset(hang,0,sizeof(hang));
37        memset(c,0,sizeof(c));
38        sum=0;
39        for(i=1;i<=n;i++)
40        {
41            scanf("%d",&size);
42            c[size]++;
43            sum+=size*size;
44        }
45        if(sum!=s*s)printf("HUTUTU!\n");
46        else 
47        {
48            if(dfs(0))printf("KHOOOOB!\n");
49            else printf("HUTUTU!\n");
50        }
51    }
52    return 1;
53}

posted on 2009-08-07 20:40 蜗牛也Coding 阅读(284) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年8月>
日一二三四五六
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜