2010年1月13日星期三.pku1185
狀態(tài)壓縮動(dòng)態(tài)規(guī)劃
pku1185:題目是中文的，而且題目很經(jīng)典，題意不再贅述。
這個(gè)題目比pku2411和sgu131兩題來說多了一行狀態(tài)需要儲(chǔ)存
因?yàn)槿绻仙闲泻痛诵杏嘘P(guān)
而且此題不再是求完美覆蓋的方式，而是求能最大的放置個(gè)數(shù)。
方法是先求出一行中的所有放置方法。
然后逐行遞推，然后在遞推的過程中枚舉當(dāng)前行狀態(tài)，如果和上兩行不沖突的話，就
進(jìn)行放置個(gè)數(shù)的更新
f[N][60][60] //N行，上一行的狀態(tài)號(hào)，上上行的狀態(tài)號(hào)
具體看代碼吧
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是對(duì)M==10的一行進(jìn)行深搜得到的最大狀態(tài)數(shù)量
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++) { //枚舉當(dāng)前行
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])) { //和上兩行狀態(tài)不沖突
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