問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1020思路:
原本以為是挺簡單的題，結(jié)果卻始終不知道怎么搜索，艾...備受打擊
雖然目前對于回溯部分的代碼理解起來已經(jīng)沒有困難，對于每次搜索都從占用最少的列開始，還是不明白為什么...
參考:
http://www.shnenglu.com/RyanWang/archive/2008/10/26/65051.aspx代碼:
1 #define MAX_LEN 42
2 #define MAX_SIZE 11
3 int size, n;
4 int used[MAX_LEN], pieces[MAX_SIZE];
5 int flag;
6
7 void
8 dfs(int depth)
9 {
10 int i, j, col, min_used=MAX_LEN;
11 if(depth == n) {
12 flag = 1;
13 return;
14 }
15 for(i=1; i<=size; i++)
16 if(used[i] < min_used) {
17 min_used = used[i];
18 col = i;
19 }
20 for(i=10; i>=1; i--) {
21 if(pieces[i]>0 && used[col]+i<=size && col+i-1<=size) {
22 for(j=col; j<=col+i-1; j++)
23 if(used[j]>min_used)
24 break;
25 if(j>col+i-1) {
26 --pieces[i];
27 for(j=col; j<=col+i-1; j++)
28 used[j] += i;
29 dfs(depth+1);
30 for(j=col; j<=col+i-1; j++)
31 used[j] -= i;
32 ++pieces[i];
33 }
34 }
35 }
36 }
37
38 int
39 main(int argc, char **argv)
40 {
41 int i, tmp, tests, sum;
42 scanf("%d", &tests);
43 while(tests--) {
44 memset(used, 0, sizeof(used));
45 memset(pieces, 0, sizeof(pieces));
46 flag = 0;
47 scanf("%d %d", &size, &n);
48 sum = 0;
49 for(i=0; i<n; i++) {
50 scanf("%d", &tmp);
51 ++pieces[tmp];
52 sum += (tmp*tmp);
53 }
54 if(sum == size*size)
55 dfs(0);
56 printf("%s\n", flag==1 ? "KHOOOOB!" : "HUTUTU!");
57 }
58 }