国产精品视频男人的天堂,欧美日韩成人一区,亚洲高清在线视频

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

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



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

2010年8月

日

一

二

三

四

五

六

統計

隨筆 - 78
文章 - 0
評論 - 96
引用 - 0

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

積分 - 94589
排名 - 261

pku 1020

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜