HDU 4539郑厂长系列故事――排兵布阵（状压DP）

基础的状压DP，首先记录先每一行可取的所哟状态（一行里互不冲突的大概160个状态），
直接套了一个4重循环居然没超时我就呵呵了
  1 //#pragma comment(linker,"/STACK:102400000,102400000")
  2 #include <map>
  3 #include <set>
  4 #include <stack>
  5 #include <queue>
  6 #include <cmath>
  7 #include <ctime>
  8 #include <vector>
  9 #include <cstdio>
 10 #include <cctype>
 11 #include <cstring>
 12 #include <cstdlib>
 13 #include <iostream>
 14 #include <algorithm>
 15 using namespace std;
 16 #define INF 1e8
 17 #define inf (-((LL)1<<40))
 18 #define lson k<<1, L, mid
 19 #define rson k<<1|1, mid+1, R
 20 #define mem0(a) memset(a,0,sizeof(a))
 21 #define mem1(a) memset(a,-1,sizeof(a))
 22 #define mem(a, b) memset(a, b, sizeof(a))
 23 #define FOPENIN(IN) freopen(IN, "r", stdin)
 24 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)
 25 template<class T> T CMP_MIN(T a, T b) { return a < b; }
 26 template<class T> T CMP_MAX(T a, T b) { return a > b; }
 27 template<class T> T MAX(T a, T b) { return a > b ? a : b; }
 28 template<class T> T MIN(T a, T b) { return a < b ? a : b; }
 29 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
 30 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }
 31 
 32 //typedef __int64 LL;
 33 //typedef long long LL;
 34 const int MAXN = 10000;
 35 const int MAXM = 100005;
 36 const double eps = 1e-13;
 37 //const LL MOD = 1000000007;
 38 
 39 int N, M;
 40 int ma[110];
 41 int dp[2][200][200];
 42 
 43 int stNum;
 44 int st[1000], num[1000];
 45 
 46 int judge(int x)
 47 {
 48     if(x & (x<<2)) return 0;
 49     return 1;
 50 }
 51 
 52 int get1(int x)
 53 {
 54     int ret = 0;
 55     while(x)
 56     {
 57         ret += x & 1;
 58         x >>= 1;
 59     }
 60     return ret;
 61 }
 62 
 63 void init()
 64 {
 65     mem1(dp);mem0(ma);
 66     stNum = 0;
 67     for(int i=0;i<(1<<M);i++) if(judge(i))
 68     {
 69         st[stNum] = i;
 70         num[stNum++] = get1(i);
 71     }
 72 }
 73 
 74 
 75 int main()
 76 {
 77     //FOPENIN("in.txt");
 78     while(~scanf("%d %d%*c", &N, &M))
 79     {
 80         init();
 81         int x, cur = 0;
 82         for(int i=1;i<=N;i++)
 83             for(int j=0;j<M;j++) {
 84                 scanf("%d", &x);
 85                 if(x==0) ma[i] |= (1<<j);
 86             }
 87         for(int i=0;i<stNum;i++) {
 88             if(st[i] & ma[1]) continue;
 89             dp[cur][i][0] = num[i];
 90         }
 91         for(int r = 2; r <= N; r ++)
 92         {
 93             cur = !cur;
 94             for(int i = 0; i < stNum; i ++)
 95             {
 96                 if(st[i] & ma[r]) continue;
 97                 for(int j = 0; j < stNum; j ++ )
 98                 {
 99                     if(st[j] & ma[r-1]) continue;
100                     int p = (st[i]<<1) | (st[i]>>1);
101                     if(st[j] & p) continue;
102                     for(int k = 0; k < stNum; k ++) if(dp[!cur][j][k] != -1)
103                     {
104                         int pp = st[i] | ((st[j]<<1) | (st[j]>>1));
105                         if(st[k] & pp) continue;
106                         dp[cur][i][j] = MAX(dp[cur][i][j], dp[!cur][j][k] + num[i]);
107                     }
108 
109                 }
110             }
111         }
112         int ans = 0;
113         for(int i=0;i<stNum;i++) for(int j=0;j<stNum;j++)
114             ans = MAX(ans, dp[cur][i][j]);
115         printf("%d
", ans);
116     }
117     return 0;
118 }
119 
120 
121 /*
122 
123 6
124 3
125 2
126 12
127 
128 */