poj1185炮兵阵地(三维状态压缩dP)

1 #include
2 #include
3 #include
4 #include
5 #include
6 using namespace std;
7 #define max(a, b) (a) > (b)?(a):(b)
8
9 int cnt, c[80], m, n;
10 char map[110][20], num[110];
11 int d[110][70][70], cur[110];
12 bool ok(int x) //判断一行中，是否合法
13 {
14 if(x&(x<<1)) return false;
15 if(x&(x<<2)) return false;
16 return true;
17 }
18 void init() //初始计算这n个 有多少种合法的状态
19 {
20 int i;
21 cnt = 0;
22 for(i = 0; i <(1<)
23 if(ok(i))
24 c[++cnt] = i;
25 }
26 bool fit(int x, int k) //判断当前行的状态是否与 地形合法
27 {
28 if(cur[k]&x) return false;
29 return true;
30 }
31 int cal(int x)
32 {
33 int sum = 0;
34 while(x)
35 {
36 sum++;
37 x = (x&(x-1)); //计算一行中1的个数，相当于每次都减去1个1
38 }
39 return sum;
40 }
41 int main()
42 {
43 int i, j, k, t, ans;
44 while(~scanf("%d%d", &m, &n))
45 {
46 if(n==0 && m==0)
47 break;
48 init();
49 for(i = 1; i <= m; i++)
50 scanf("%s", map[i]);
51 for(i = 1; i <= m; i++)
52 {
53 cur[i] = 0;
54 for(j = 0; j )
55 {
56 if(map[i][j]==‘H‘)
57 cur[i] += 1;
58 if(j != n-1)
59 cur[i] = (cur[i]<<1);
60 }
61 }
62 memset(d, -1, sizeof(d));
63
64 for(i = 1; i <= cnt; i++) //初始第1行
65 {
66 num[i] = cal(c[i]);
67 if(fit(c[i], 1))
68 d[1][1][i] = num[i];
69 }
70 for(i = 2; i <= m; i++)
71 for(t = 1; t <= cnt; t++)
72 {
73 if(!fit(c[t], i))
74 continue;
75 for(j = 1; j <= cnt; j++)
76 {
77 if(c[t]&c[j]) continue; //判断与上上行合法
78 for(k = 1; k <= cnt; k++)
79 {
80 if(c[t]&c[k]) continue; //判断与上行合法
81 if(d[i-1][j][k]==-1) continue;
82 d[i][k][t] = max(d[i][k][t], d[i-1][j][k]+num[t]);
83 }
84 }
85 }
86
87 ans = 0;
88 for(i = 1; i <= m; i++)
89 for(j = 1; j <= cnt; j++)
90 for(k = 1; k <= cnt; k++)
91 ans = max(ans, d[i][j][k]);
92 printf("%d\n", ans);
93 }
94 return 0;
95 }