亚洲精品久久久久,国产精品分类,一本色道久久

pku 1020

2009年8月7日

題目鏈接：PKU 1020 Anniversary Cake

分類：DFS應(yīng)用

題目分析與算法原型：
題目大意就是給你些整邊長小正方形問你能否拼成一個(gè)給定的整邊長的大正方形。看數(shù)據(jù)范圍和題目類型，可以知道，先判斷一下所有小正方形面積之和是否恰為s^2之后，就應(yīng)該dfs了.
大致做法是：按從左到右從上到下的順序來放小正方形，先將大正方形看成一個(gè)二維數(shù)組，定義一個(gè)數(shù)組hang[],hang[i]表示第i列前面的hang[i]行已經(jīng)被占用了，然后先找到hang[i]最小的那個(gè)以它作為下一個(gè)放正方形的左上頂點(diǎn)，接著每次從大到小枚舉所剩的正方形看能否放入（可以直接從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 閱讀(317) 評(píng)論(0) 編輯收藏引用

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



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

pku 1020

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜