国产精品9999久久久久,国产一区二区精品久久岳,国产精品久久久久久久久

pku 1020

2009年8月7日

題目鏈接：PKU 1020 Anniversary Cake

分類：DFS應(yīng)用

題目分析與算法原型：
題目大意就是給你些整邊長小正方形問你能否拼成一個給定的整邊長的大正方形。看數(shù)據(jù)范圍和題目類型，可以知道，先判斷一下所有小正方形面積之和是否恰為s^2之后，就應(yīng)該dfs了.
大致做法是：按從左到右從上到下的順序來放小正方形，先將大正方形看成一個二維數(shù)組，定義一個數(shù)組hang[],hang[i]表示第i列前面的hang[i]行已經(jīng)被占用了，然后先找到hang[i]最小的那個以它作為下一個放正方形的左上頂點，接著每次從大到小枚舉所剩的正方形看能否放入（可以直接從10到1枚舉小正方形的邊長），若能放入，再接著DFS.......

Code:

1

#include<stdio.h>
2

#include<string.h>
3

int t,s,n,hang[42],c[11];
4

bool 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

}
29

int 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 閱讀(309) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

pku 1020

導(dǎo)航

統(tǒng)計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜