2010年1月13日星期三.pku1185
狀態壓縮動態規劃
pku1185:題目是中文的，而且題目很經典，題意不再贅述。
這個題目比pku2411和sgu131兩題來說多了一行狀態需要儲存
因為如果上上行和此行有關
而且此題不再是求完美覆蓋的方式，而是求能最大的放置個數。
方法是先求出一行中的所有放置方法。
然后逐行遞推，然后在遞推的過程中枚舉當前行狀態，如果和上兩行不沖突的話，就
進行放置個數的更新
f[N][60][60] //N行，上一行的狀態號，上上行的狀態號
具體看代碼吧
1
2 /*
3 * SOUR:pku1185
4 * ALGO:State Compression DP
5 * DATE: 2010年 01月 13日 星期三 13:57:49 CST
6 * COMM:4 http://www.shnenglu.com/schindlerlee
7 * */
8 #include<iostream>
9 #include<cstdio>
10 #include<cstdlib>
11 #include<cstring>
12 #include<algorithm>
13 using namespace std;
14 typedef long long LL;
15 const int maxint = 0x7fffffff;
16 const long long max64 = 0x7fffffffffffffffll;
17
18 #define bin(i) (1 << (i))
19 #define low(i) ((i) & -(i))
20 #define SL(i) ((i) << 1)
21 #define SR(i) ((i) >> 1)
22
23 void ckmax(int &a, int b)
24 { if (a < b) a = b; }
25
26 const int N = 102;
27 const int M = 10;
28
29 //60是對M==10的一行進行深搜得到的最大狀態數量
30 int f[N][60][60], n, m, terrain[N], full;
31 int s[60], top, c[60];
32
33 int legal(int x)
34 {
35 int b = 0, cnt = 0, c;
36 while (x > 0) {
37 cnt++;
38 c = low(x);
39 if (SL(b) & x || SL(SL(b)) & x) {
40 return -1;
41 }
42 x ^= c;
43 b = c;
44 }
45 return cnt;
46 }
47
48 void preprocess()
49 {
50 int i, j, cnt;
51 for (i = 0; i <= full; i++) {
52 if ((cnt = legal(i)) >= 0) {
53 s[top] = i, c[top] = cnt, top++;
54 }
55 }
56 }
57
58 bool contradict(int cur, int s1, int s2)
59 { return (cur & s1) || (cur & s2); }
60
61 int main()
62 {
63 int i, j, k;
64 char str[12];
65 while (scanf("%d%d\n", &n, &m) == 2) {
66 full = bin(m) - 1;
67 preprocess();
68
69 for (i = 1; i <= n; i++) {
70 scanf("%s\n", str);
71 int tmp = 0;
72 for (j = 0; j < m; j++) {
73 tmp <<= 1;
74 if (str[j] == 'H') {
75 tmp |= 1;
76 }
77 }
78 terrain[i] = tmp;
79 }
80
81 for (i = 1; i <= n; i++) {
82 for (j = 0; j < top; j++) { //枚舉當前行
83 int cur = s[j], curcnt = c[j];
84 if (cur & terrain[i]) {
85 continue;
86 } //不符合第i行地形要求
87
88 for (int k1 = 0; k1 < top; k1++) { //枚舉前兩行
89 for (int k2 = 0; k2 < top; k2++) {
90 if (!contradict(cur, s[k1], s[k2])) { //和上兩行狀態不沖突
91 ckmax(f[i][j][k1], f[i - 1][k1][k2] + curcnt);
92 }
93 }
94 }
95 }
96 }
97
98 int res = 0;
99 for (i = 0; i < top; i++) {
100 for (j = 0; j < top; j++) {
101 ckmax(res, f[n][i][j]);
102 }
103 }
104 printf("%d\n", res);
105 }
106 return 0;
107 }
108
109