PKU1038，动态规划，用的三进制压缩状态（不知道和二进制那个快，毕竟计算机这个东西是二进制的），感觉没用的状态有点多，所以改成了记忆化搜索，另外第一次排到了速度的23名。。
PKU1038
1/**//*
2
Task: pku1038
3Author: DMKaplony
4Date: 01/03/2010 18:51:04 China Standard Time
5State: AC @ 03/03/2010 09:04:19 China Standard Time
6 Speed 23
7Memo: DP--Forxcc0322
8
*/
9
10#include <iostream>
11
12#define INF 0x7FFFFFFF
13#define gmax(a,b) ((a)>(b)?(a):(b))
14#define MAXN 400
15#define MAXM 11
16#define MAXS 177147
17
18using namespace std;
19
20struct QNode
{
21 int row;
22 int state;
23 int f;
24
void SetData(int R, int S, int F){
25 row = R;
26 state = S;
27 f = F;
28
}
29 };
30
31QNode Q[MAXS];
32int h, t, maxq;
33bool block[MAXN][MAXM];
34int pnt[2][MAXS];
35int n, m, k;
36int v[MAXM];
37int x;
38int state;
39int ans;
40
41void DfsExtend(int dep, int got){
42 if (!dep){
43 int newstate = 0;
44 for (int i=m; i; i--){
45 newstate *= 3;
46 newstate += v[i] - 1;
47 }
48 if (x < n && pnt[(x + 1)& 1][newstate] == -1){
49 if (++t == maxq)
50 t = 0;
51 Q[t].SetData(x + 1, newstate, got);
52 pnt[(x + 1)& 1][newstate] = t;
53 }
54 else
55 if (got > Q[pnt[(x + 1)& 1][newstate]].f)
56 Q[pnt[(x + 1)&1][newstate]].f = got;
57 return;
58 }
59 if (dep >= 3 && !v[dep] && !v[dep - 1] && !v[dep - 2]){
60 if (block[x + 2][dep])
61 v[dep] = 3;
62 else
63 v[dep] = 2;
64 if (block[x + 2][dep - 1])
65 v[dep - 1] = 3;
66 else
67 v[dep - 1] = 2;
68 if (block[x + 2][dep - 2])
69 v[dep - 2] = 3;
70 else
71 v[dep - 2] = 2;
72
73 DfsExtend(dep - 3, got + 1);
74
75 v[dep] = v[dep - 1] = v[dep - 2] = 0;
76 }
77 if (dep >= 2 && !block[x + 2][dep] && !block[x + 2][dep - 1]
78 && !v[dep] && !v[dep - 1]){
79 v[dep] = 3;
80 v[dep - 1] = 3;
81
82 DfsExtend(dep - 2, got + 1);
83
84 v[dep] = v[dep - 1] = 0;
85 }
86 //
87 if (block[x + 2][dep]){
88 int tmp = v[dep];
89 v[dep] = 3;
90 DfsExtend(dep - 1, got);
91 v[dep] = tmp;
92 }
93 else
94 if (!v[dep]){
95 v[dep] = 1;
96 DfsExtend(dep - 1, got);
97 v[dep] = 0;
98 }
99 else{
100 DfsExtend(dep - 1, got);
101 }
102 }
103
104
105void Extend(int x, int state, int got){
106 memset(v, 0, sizeof(v));
107 while (state){
108 v[++v[0]] = state % 3;
109 state /= 3;
110 }
111 DfsExtend(m, got);
112 }
113
114int QPow(int x, int y){
115 if (y == 0)
116 return 1;
117 else
118 if (y == 1)
119 return x;
120 int tmp = QPow(x, y >> 1);
121 tmp *= tmp;
122 if (y & 1)
123 return tmp * x;
124 else
125 return tmp;
126 }
127int main(){
128 int cases;
129 scanf("%d", &cases);
130 while (cases--){
131 scanf("%d %d %d", &n, &m, &k);
132 memset(block, 0, sizeof(block));
133
134 int i;
135 for (i=1; i<k+1; i++){
136 int x, y;
137 scanf("%d %d", &x, &y);
138 block[x][y] = true;
139 }
140 for (i=1; i<m+1; i++){
141 block[n + 1][i] = true;
142 }
143
144 memset(pnt, 0xFF, sizeof(pnt));
145 int newstate = 0;
146 for (int j=m; j; j--){
147 newstate *= 3;
148 if (block[2][j])
149 newstate += 2;
150 else
151 if (block[1][j])
152 newstate += 1;
153 }
154 ans = 0;
155 h = 0;
156 t = 0;
157 maxq = QPow(3, m + 2);
158 if (++t == maxq)
159 t = 0;
160 Q[t].SetData(1, newstate, 0);
161 pnt[1][newstate] = t;
162 x = 1;
163 while (h != t){
164 if (++h == maxq)
165 h = 0;
166 if (x != Q[h].row){
167 memset(pnt[(x + 1)&1], 0xFF, sizeof(pnt[(x + 1)& 1]));
168 x++;
169 }
170 state = Q[h].state;
171 ans = gmax(ans, Q[h].f);
172 Extend(x, state, Q[h].f);
173 }
174 printf("%d\n", ans);
175 }
176 return 0;
177 }
178