oyjpArt 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://www.cppblog.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}