洛谷 P1924 poj 1038

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 const int N = 59050;
 6 /*pre表示你枚举的上一个状态，now表示你现在枚举的状态*/
 7 int dp[2][N], mp[160][15], pre[12], now[12], n, m, d, cur;
 8 int base[] = {0,1,3,9,27,81,243,729,2187,6561,19683,59049};
 9 void init(){
10     memset(mp, 0, sizeof(mp));
11     memset(dp, -1, sizeof(dp));
12 }
13 /*3进制转10进制*/
14 int trans(int *t){
15     int ans = 0;
16     for(int i = 1; i <= m; i++)
17       ans += t[i] * base[i];
18     return ans;
19 }
20 /*10进制转3进制*/
21 void chan(int t, int *p){
22     for(int i = 1; i <= m; i++)
23       p[i] = t % 3, t /= 3;
24     return ;
25 }
26 /*i为当前行，j为当前状态，cnt为格子数目，tmp为当前压缩后整行状态*/
27 void dfs(int i, int j, int cnt, int tmp){
28     int k;
29     dp[i & 1][tmp] = max(dp[i & 1][tmp], cnt);
30     if(j >= m) return ;
31     /*放上3行2列的格子
32       如果该层状态和前一层的状态都允许 那么就放上格子继续搜下去*/
33     if(!pre[j] && !pre[j + 1] && !now[j] && !now[j + 1]){
34         now[j] = now[j + 1] = 2;  //放格子之后状态就都是2了
35         k = trans(now); dfs(i, j + 2, cnt + 1, k);//因为两格都被覆盖，跳过去搜
36         now[j] = now[j + 1] = 0;  //回溯
37     }
38     /*放上2行3列的格子
39      这个就只跟你当前的状态有关了*/
40     if(j < m - 1 && !now[j] && !now[j + 1] && !now[j + 2]){
41         now[j] = now[j + 1] = now[j + 2] = 2; //同样修改 搜下去 回溯
42         k = trans(now);  dfs(i, j + 3, cnt + 1, k);
43         now[j] = now[j + 1] = now[j + 2] = 0;
44     }
45     dfs(i, j + 1, cnt, tmp);
46     return ;
47 }
48 int main(){
49     int T, x, y;
50     scanf("%d", &T);
51     while(T--){
52         init();
53         scanf("%d%d%d", &n, &m, &d);
54         for(int i = 1; i <= d; i++){
55             scanf("%d%d", &x, &y);
56             mp[x][y] = 1;
57         }
58         for(int i = 1; i <= m; i++)
59           pre[i] = 2;
60         int tmp = trans(pre);
61         dp[0][tmp] = 0;  //对于第0行来说，只有啥都不能放这一种状态 将该状态价值为0
62         for(int i = 1; i <= n; i++){
63             memset(dp[i & 1], -1, sizeof(dp[i & 1]));  //初始化本次要用的dp数组
64             for(int j = 0; j < base[m + 1]; j++){  //枚举上一行的状态
65                 /* 如果上一行的状态dp数组为-1，说明上一层的该状态根本达不到，那么就不能用来转移*/
66                 if(dp[i + 1 & 1][j] == -1) continue;
67                 chan(j, pre); //将上一层的状态转换成3进制
68                 for(int k = 1; k <= m; k++)  //k为j状态往后移一格的状态
69                   if(mp[i][k]) now[k] = 2; //如果此时第k位无法覆盖，那么就为状态为2
70                 /*不然，2状态变为1状态，其余为0(根据状态的定义就可以得出)*/
71                   else now[k] = max(pre[k] - 1, 0); 
72                 cur = dp[i + 1 & 1][j];  //cur表示上一层该状态达到的最大价值
73                 dfs(i, 1, cur, trans(now)); //dfs转移 因为第一格前为第0格不能放，所以状态为1
74             }
75         }
76         int ans = 0;
77         for(int i = 0; i < base[m + 1]; i++)
78           ans = max(ans, dp[n & 1][i]);
79         printf("%d\n", ans);
80     }
81     return 0;
82 }