状压DP SGU 223 Little Kings

  1 /*
  2     题意：n*n的矩阵，放置k个king，要求king互相不能攻击，即一个king的8个方向都没有另外的king，求方案个数
  3     状态压缩DP：dp[i][num[j]][s] 代表在第i行，放置num[j]个king，其状态为s时的方案数
  4                 首先对state进行筛选，即一行king左右相邻没有另外的king，确定tot
  5                 接着对第一行进行处理，对2~n行DP递推，同样要满足各种条件限制，num个数和不超过k，s1,s2状态也要ok
  6                 最后累加放置k个king时的方案数
  7     详细解释：http://blog.csdn.net/roney_win/article/details/9617081
  8 */
  9 #include <cstdio>
 10 #include <iostream>
 11 #include <algorithm>
 12 #include <cstring>
 13 #include <cmath>
 14 #include <map>
 15 #include <set>
 16 #include <string>
 17 using namespace std;
 18 
 19 const int MAXN = 15;
 20 const int INF = 0x3f3f3f3f;
 21 long long dp[15][110][150];
 22 int st[150];
 23 int num[150];
 24 
 25 bool ok(int x)
 26 {
 27     if ((x & (x << 1)) == 0)    return true;
 28     else    return false;
 29 }
 30 
 31 int init_state(int n, int k)
 32 {
 33     int tot = 1 << n;
 34     int cnt = 0;
 35     for (int i=0; i<tot; ++i)
 36     {
 37         if (ok (i))
 38         {
 39             num[cnt] = 0;
 40             int t = i;
 41             while (t)
 42             {
 43                 num[cnt] += (t & 1);
 44                 t >>= 1;
 45             }
 46             st[cnt++] = i;
 47         }
 48     }
 49 
 50     return cnt;
 51 }
 52 
 53 int main(void)        //SGU 223 Little Kings
 54 {
 55     #ifndef ONLINE_JUDGE
 56     freopen ("E.in", "r", stdin);
 57     #endif
 58 
 59     int n, k;
 60     while (~scanf ("%d%d", &n, &k))
 61     {
 62         int tot = init_state (n, k);
 63         memset (dp, 0, sizeof (dp));
 64 
 65         for (int s=0; s<tot; ++s)
 66         {
 67             if (num[s] <= k)
 68             {
 69                 dp[1][num[s]][s]++;
 70             }
 71         }
 72 
 73         for (int i=1; i<=n-1; ++i)
 74         {
 75             for (int j=0; j<=k; ++j)
 76             {
 77                 for (int s1=0; s1<tot; ++s1)
 78                 {
 79                     if (num[s1] <= j)
 80                     {
 81                         int res = j - num[s1];
 82                         for (int s2=0; s2<tot; ++s2)
 83                         {
 84                             if (num[s2] <= res)
 85                             {
 86                                 if ((st[s1] & st[s2]) == 0)
 87                                 {
 88                                     if (((st[s1] & (st[s2] << 1)) == 0) && ((st[s1] & (st[s2] >> 1)) == 0))
 89                                     {
 90                                         dp[i+1][j][s1] += dp[i][res][s2];
 91                                     }
 92                                 }
 93                             }
 94                         }
 95                     }
 96                 }
 97             }
 98         }
 99 
100         long long ans = 0;
101         for (int s=0; s<tot; ++s)
102         {
103             if (num[s] <= k)
104             {
105                 ans += dp[n][k][s];
106             }
107         }
108 
109         printf ("%I64d
", ans);
110 
111     }
112 
113     return 0;
114 }
115 
116 
117 /*
118 Test #1
119 */
编译人生，运行世界！