oyjpArt ACM/ICPC算法程序設(shè)計(jì)空間

PKU2286 The Rotation Game
迭代深搜+剪枝

狀態(tài)數(shù)很大，很難壓縮。試圖減少狀態(tài)，無(wú)果。DFS深度太大，故采用迭代深搜。
注意到這個(gè)題目其實(shí)解并不深 但如果不迭代深搜 會(huì)使搜索陷入深層
剪枝：對(duì)于中間8個(gè)格子 通過變換使其相等的最小代價(jià)為
8-Max(1的個(gè)數(shù),2的個(gè)數(shù),3的個(gè)數(shù))

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個(gè)方法：
1.TreeDP(樹形DP)
這個(gè)應(yīng)該是看到題目后第一個(gè)想到的。因?yàn)轭}目要求的最大人數(shù)應(yīng)該就是標(biāo)準(zhǔn)的TreeDP做法。但是關(guān)于是否解唯一，做法又有很多，可以設(shè)置一個(gè)uniq數(shù)組來在DP的時(shí)候加以判斷。規(guī)則如下：
設(shè)一個(gè)節(jié)點(diǎn)x 取x的時(shí)候得值為 dp[x][1]，不取為dp[x][0]
若dp[x][1] = dp[x][0] 那么這一點(diǎn)本身一定不唯一
其他情況 假定父節(jié)點(diǎn)x 有k個(gè)子節(jié)點(diǎn)Yk 則由狀態(tài)轉(zhuǎn)移中子節(jié)點(diǎn)的唯一性來判斷

2.貪心
貪心的方法比較容易想到 但是證明唯一性不容易
唯一性判斷:
設(shè)一個(gè)節(jié)點(diǎn)y的父節(jié)點(diǎn)為x, x的父節(jié)點(diǎn)位f
如果y已經(jīng)被選 x沒有被選 而f也沒有被選或者根本不存在（x為根）
如果x的所有除y以外的子節(jié)點(diǎn)都有被選
則 x和y的被選性可以交換 故不唯一
這個(gè)方法不知道如何證明 不過確實(shí)可以過題

3.二分圖匹配
題目給出的圖滿足節(jié)點(diǎn)和子節(jié)點(diǎn)的取子情況不能重復(fù)的情況,因此我們很好根據(jù)這個(gè)構(gòu)造二分圖.假設(shè)有X集合和Y集合,如果某節(jié)點(diǎn)x處在X集合中,則其所有子節(jié)點(diǎn)均處在y集合中,反之亦然. 這樣題目就轉(zhuǎn)化了求最大獨(dú)立集的問題(集合中任意兩點(diǎn)沒有邊相接), 根據(jù)二分圖的知識(shí),假設(shè)二分圖匹配為M, 我們可以將其轉(zhuǎn)化成N-M;
而判斷唯一性 方法是從Y集合(當(dāng)然從X集合也行)做BFS, 或者使用強(qiáng)連通分支的方法判斷某個(gè)匹配是否唯一.
這個(gè)算法在這篇文章中有詳細(xì)敘述:
http://www.shnenglu.com/sicheng/archive/2007/08/07/29530.html

PKU3182 The Grove
題目的意思是讓你找到一條最短的回路，使這條回路經(jīng)過一個(gè)點(diǎn)（題目中的'*')　并且能夠環(huán)繞一片連續(xù)的‘Ｘ’區(qū)域。
從題目的‘最短’和‘環(huán)繞’上考慮　我們應(yīng)該是在進(jìn)行ＢＦＳ的時(shí)候進(jìn)行一些符合題目條件的限制，讓我們順利找到這樣一個(gè)環(huán)繞X區(qū)域的回路。
于是我們便轉(zhuǎn)化成了加限制的BFS（限制他會(huì)環(huán)繞的走一圈）。如何限制呢？如果我們直接做BFS的話 勢(shì)必會(huì)從‘X’區(qū)域的一邊擴(kuò)展到其另一邊
(比如＊在Ｘ區(qū)域的下方　那么就會(huì)分別從左邊和右邊擴(kuò)展到Ｘ區(qū)域的上方．但是我們需要的是從右邊（當(dāng)然左邊也行）擴(kuò)展到上方，然后從上方沿著左邊擴(kuò)展到下方．
到這里可能有點(diǎn)思路了，我們必須要限制從下方沿著Ｘ區(qū)域向左的向上ＢＦＳ擴(kuò)展．于是我們考慮在Ｘ區(qū)域的最上層畫一條線．凡是從Ｘ區(qū)域左邊擴(kuò)展到這條線上面去的路線我們均在ＢＦＳ中終止．但是從右邊擴(kuò)展上去的允許．當(dāng)然從上邊沿著左邊擴(kuò)展到下面的也允許．由于一個(gè)點(diǎn)最多被ＢＦＳ擴(kuò)展２次（即從左邊向上擴(kuò)展的時(shí)候和從上沿著左邊向下擴(kuò)展的時(shí)候）所以我們定義一個(gè)dist[x][y][f]數(shù)組，然后對(duì)棋盤做有限制的ＢＦＳ，相信這樣足以解出此題．

PKU1549 Bright Bracelet
我真是太弱了。這道題被我折騰了2個(gè)小時(shí)，加了各種各樣的上下界剪枝條，都沒有剪過。最后在ZZN的提示下，用狀態(tài)壓縮DP搞定了這道題。看來我要好好反省下了。也許搜索強(qiáng)人能過掉吧，請(qǐng)教教我。
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}