|
|
Posted on 2007-08-15 10:07 oyjpart 閱讀(2080) 評論(5) 編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽
PKU2286 The Rotation Game
迭代深搜+剪枝
狀態數很大，很難壓縮。試圖減少狀態，無果。DFS深度太大，故采用迭代深搜。
注意到這個題目其實解并不深 但如果不迭代深搜 會使搜索陷入深層
剪枝：對于中間8個格子 通過變換使其相等的最小代價為
8-Max(1的個數,2的個數,3的個數)
code follows:
1 //by oyjpArt
2#include <string.h>
3#include <stdio.h>
4
5const int N = 25;
6int a[N], ans[100];
7
8#define Max(a, b) ((a)>(b)?(a):(b))
9
10int f[8][7][2] = {
11 { {1,23}, {3,1}, {7,3}, {12,7}, {16,12}, {21,16}, {23,21} },
12 { {2,24}, {4,2}, {9,4}, {13,9}, {18,13}, {22,18}, {24,22} },
13 { {11,5}, {10,11}, {9,10}, {8,9}, {7,8}, {6,7}, {5,6} },
14 { {20,14}, {19,20}, {18,19}, {17,18}, {16,17}, {15,16}, {14,15} },
15 { {24,2}, {22,24}, {18,22}, {13,18}, {9,13}, {4,9}, {2,4} },
16 { {23,1}, {21,23}, {16,21}, {12,16}, {7,12}, {3,7}, {1,3} },
17 { {14,20}, {15,14}, {16,15}, {17,16}, {18,17}, {19,18}, {20,19} },
18 { {5,11}, {6,5}, {7,6}, {8,7}, {9,8}, {10,9}, {11,10} }
19};
20
21int Len, ANS;
22
23int check() {
24 int ret = a[7];
25 if(a[8]!=ret || a[9]!=ret || a[12]!=ret || a[13]!=ret ||
26 a[16]!=ret || a[17]!=ret || a[18]!=ret)
27 return 0;
28 return ANS = ret;
29}
30
31int cal() {
32 int num[4];
33 memset(num, 0, sizeof(num));
34 num[a[7]]++;
35 num[a[8]]++;
36 num[a[9]]++;
37 num[a[12]]++;
38 num[a[13]]++;
39 num[a[16]]++;
40 num[a[17]]++;
41 num[a[18]]++;
42 return 8-Max(num[3], Max(num[2], num[1]));
43}
44
45
46int DFS(int now) {
47
48 int i, b[N], j, t;
49
50 if(now == Len)
51 return check();
52
53 int c = cal();
54 if(now + c > Len)
55 return 0;
56
57 for(i = 0; i < 8; ++i) {
58 ans[now] = i;
59 memcpy(b, a, sizeof(a));
60 for(j = 0; j < 7; ++j)
61 a[f[i][j][1]] = b[f[i][j][0]];
62 t = DFS(now+1);
63 memcpy(a, b, sizeof(b));
64 if(t != 0)
65 return t;
66 }
67 return 0;
68}
69
70int main() {
71
72// freopen("t.in", "r", stdin);
73
74 int i, t;
75 while(scanf("%d", &a[1]), a[1]) {
76 for(i = 2; i <= 24; ++i)
77 scanf("%d", &a[i]);
78
79 if(check() != 0) {
80 printf("No moves needed\n%d\n", a[7]);
81 continue;
82 }
83
84 Len = 1;
85 while( (t = DFS(0)) == 0)
86 Len++;
87
88 int i;
89 for(i=0; i<Len; ++i)
90 putchar(ans[i]+'A');
91 printf("\n%d\n", ANS);
92 }
93 return 0;
94}
PKU3342 Party at Hali-Bula
這是昨天的比賽題。我搞了好久才搞定。真是太弱了。唉。
有3個方法：
1.TreeDP(樹形DP)
這個應該是看到題目后第一個想到的。因為題目要求的最大人數應該就是標準的TreeDP做法。但是關于是否解唯一，做法又有很多，可以設置一個uniq數組來在DP的時候加以判斷。規則如下：
設一個節點x 取x的時候得值為 dp[x][1]，不取為dp[x][0]
若dp[x][1] = dp[x][0] 那么這一點本身一定不唯一
其他情況 假定父節點x 有k個子節點Yk 則由狀態轉移中子節點的唯一性來判斷
2.貪心
貪心的方法比較容易想到 但是證明唯一性不容易
唯一性判斷:
設一個節點y的父節點為x, x的父節點位f
如果y已經被選 x沒有被選 而f也沒有被選或者根本不存在（x為根）
如果x的所有除y以外的子節點都有被選
則 x和y的被選性可以交換 故不唯一
這個方法不知道如何證明 不過確實可以過題
3.二分圖匹配
題目給出的圖滿足節點和子節點的取子情況不能重復的情況,因此我們很好根據這個構造二分圖.假設有X集合和Y集合,如果某節點x處在X集合中,則其所有子節點均處在y集合中,反之亦然. 這樣題目就轉化了求最大獨立集的問題(集合中任意兩點沒有邊相接), 根據二分圖的知識,假設二分圖匹配為M, 我們可以將其轉化成N-M;
而判斷唯一性 方法是從Y集合(當然從X集合也行)做BFS, 或者使用強連通分支的方法判斷某個匹配是否唯一.
這個算法在這篇文章中有詳細敘述:
http://m.shnenglu.com/sicheng/archive/2007/08/07/29530.html
PKU3182 The Grove
題目的意思是讓你找到一條最短的回路，使這條回路經過一個點（題目中的'*') 并且能夠環繞一片連續的‘Ｘ’區域。
從題目的‘最短’和‘環繞’上考慮 我們應該是在進行ＢＦＳ的時候進行一些符合題目條件的限制，讓我們順利找到這樣一個環繞X區域的回路。
于是我們便轉化成了加限制的BFS（限制他會環繞的走一圈）。如何限制呢？如果我們直接做BFS的話 勢必會從‘X’區域的一邊擴展到其另一邊
(比如＊在Ｘ區域的下方 那么就會分別從左邊和右邊擴展到Ｘ區域的上方．但是我們需要的是從右邊（當然左邊也行）擴展到上方，然后從上方沿著左邊擴展到下方．
到這里可能有點思路了，我們必須要限制從下方沿著Ｘ區域向左的向上ＢＦＳ擴展．于是我們考慮在Ｘ區域的最上層畫一條線．凡是從Ｘ區域左邊擴展到這條線上面去的路線我們均在ＢＦＳ中終止．但是從右邊擴展上去的允許．當然從上邊沿著左邊擴展到下面的也允許．由于一個點最多被ＢＦＳ擴展２次（即從左邊向上擴展的時候和從上沿著左邊向下擴展的時候）所以我們定義一個dist[x][y][f]數組，然后對棋盤做有限制的ＢＦＳ，相信這樣足以解出此題．
PKU1549 Bright Bracelet
我真是太弱了。這道題被我折騰了2個小時，加了各種各樣的上下界剪枝條，都沒有剪過。最后在ZZN的提示下，用狀態壓縮DP搞定了這道題。看來我要好好反省下了。也許搜索強人能過掉吧，請教教我。
code follows:
1//by oyjpArt
2#include <stdio.h>
3#include <string.h>
4
5const int MAXINT = 2139062143;
6
7int n;
8int cost[8];
9char bb[11][10];
10int b[11][10];
11int dp[2048][8][8];
12int two[12];
13
14int ones(int x) {
15 int c = 0;
16 while(x != 0) {
17 x &= (x-1);
18 c++;
19 }
20 return c;
21}
22
23#define Min(a, b) ((a)<(b)?(a):(b))
24
25int main() {
26
27 int i, j;
28 two[0] = 1;
29 for(i = 1; i <= 11; ++i)
30 two[i] = two[i-1]<<1;
31 while( scanf("%d", &n), n != 0) {
32 for(i = 0; i < 8; ++i)
33 scanf("%d", &cost[i]);
34 for(i = 0; i < n; ++i) {
35 scanf("%s", bb[i]);
36 for(j = 0; j < 8; j++)
37 b[i][j] = bb[i][j]-'A';
38 }
39 int tot = two[n]-1;
40 for(i = 0; i <= tot; ++i)
41 memset(dp[i], 127, sizeof(dp[i]));
42
43 for(i = 0; i < 8; ++i) {
44 int l = b[0][i], r = b[0][(i+4)%8];
45 dp[two[0]][l][r] = cost[l] + cost[r];
46 }
47 int x, p, q, k;
48 for(i = 1; i <= n-1; ++i) {
49 if(i == n-1)
50 memset(cost, 0, sizeof(cost));
51 for(x = 1; x <= tot; ++x) {
52 if(ones(x) != i)
53 continue;
54 for(p = 0; p < 8; ++p)
55 for(q = 0; q < 8; ++q)
56 if(dp[x][p][q] != MAXINT)
57 for(j = 0; j < n; ++j)
58 if( (two[j]&x) == 0 )
59 for(k = 0; k < 8; ++k) {
60 int l = b[j][k], r = b[j][(k+4)%8];
61 if(r == p) {
62 if(i == n-1)
63 if(l != q) continue;
64 dp[x+two[j]][l][q] = Min(dp[x+two[j]][l][q], dp[x][p][q]+cost[l]);
65 }
66 if(l == q) {
67 if(i == n-1)
68 if(r != p) continue;
69 dp[x+two[j]][p][r] = Min(dp[x+two[j]][p][r], dp[x][p][q]+cost[r]);
70 }
71 }
72 }
73 }
74 int ans = MAXINT;
75 for(i = 0; i < 8; ++i)
76 for(j = 0; j < 8; ++j)
77 ans = Min(ans, dp[tot][i][j]);
78
79 if(ans == MAXINT)
80 printf("impossible\n");
81 else
82 printf("%d\n", ans);
83 }
84 return 0;
85}
Feedback
請教：1549沒看懂。怎樣壓縮狀態呢？二進制在這里表示什么呢？為什么是2048？
一共有11個珠子 用11個2進制位來表示是否已經加入到當前的串中，即供需要2^11 = 2048來表示
謝謝大牛!也許是我太笨了吧，還是沒看懂。:)
dp[K][i][j]是表示什么意思?
# re: 再說幾道題[未登錄] 回復 更多評論
2007-09-03 23:29 by
不好意思 沒說清楚
dp[2048][8][8]中的第一維是代表當前那些珠子已經加入到串中。
比如如果1，2，4顆珠子加入 則第一維為(00000001011)B
所謂加入 就是這顆珠子是否已經使用
后面2維分別代表連續的珠串中最左端和最右端的珠子是什么顏色的（一共8種顏色）
之所以這樣設置DP 是因為在不斷加入珠子的過程中始終成為一連串，而決定一個狀態的只有左右兩個珠子的顏色。所以這樣設置DP之后就可以達到無后效性。
嗯~pku2286在您的啟發下過掉了～
太感謝了～
歡迎也來看我們的blog~
|