BZOJ 1087 [SCOI2005]互不侵犯King 【状压dp】

BZOJ 1087 [SCOI2005]互不侵犯King

Description

　　在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上
左下右上右下八个方向上附近的各一个格子，共8个格子。

Input

　　只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）

Output

　　方案数。

Sample Input

3 2

Sample Output

题解：

题目描述非常简洁，做起来。。。。

这道题一开始想---搜索，可是会T。或者组合数？发现推不出。。。

好吧，那还是试试状压 dp 吧。。。

对于这类棋盘类问题，一般都要状压。

一开始想，如果要记录全盘状态，存不下啊！！！后来经 dalao 指点，恍然大悟，当前行只与上一行有关系，因为它的范围只有附近八个格子。。（诶，是我太弱了）

这样我们设 dp[i][j][k] 为做到第 i 行，共放了 j 个王，第 i 行的状态为 k。

这样一来我们就好推了。 dp[i][j][k]= dp[i-1][j-num[i]][last] （num[i] 表示第 i 行放多少个王，last 表示第 i-1 行的状态）

还剩下一个问题：怎么判断合不合法，能不能放。

这里就要用到强大的位运算技巧了。。。%dalao （状压 dp 题，位运算一定要熟练掌握啊！！！）

判断同一行相邻两个是否合法：只需要 i & (i<<1) ，这样错开来，如果为1就说明在某一位置，它的两边有王，不合法；

判断上下两行的话就要两次了：既要 i<<1 ，又要 i>>1 （因为两行状态不同，所以左右两边都要判一下，同一行的话往左移，往右移效果是一样的）

贴代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,k,num[1005];
 4 long long dp[10][1005][1005];
 5 bool flag[1005];
 6 long long ans;
 7 int main()
 8 {
 9     scanf("%d%d",&n,&k);
10     for (int i=0; i<(1<<n); i++)
11       if (!(i&(i<<1)))
12       {
13           flag[i]=true;
14           int t=i;
15           while (t)
16           {
17               num[i]+=(t&1);
18               t>>=1;
19           }
20           dp[1][num[i]][i]=1;
21       }
22     for (int i=2; i<=n; i++)
23       for (int j=0; j<=k; j++)
24         for (int now=0; now<(1<<n); now++)
25         {
26             if (!flag[now]) continue;
27             if (num[now]>j) continue;
28             for (int last=0; last<(1<<n); last++)
29             {
30                 if (!flag[last]) continue;
31                 if ((last & now) || ((now<<1)&last) || ((now>>1)&last)) continue;
32                 dp[i][j][now]+=dp[i-1][j-num[now]][last];
33             }
34         }
35     for (int i=0; i<(1<<n); i++)
36       ans+=dp[n][k][i];
37     cout<<ans<<endl;
38     return 0;
39 }

View Code

dp还是欠缺啊！！！要多练啊！！！dp很重要！！！

加油加油加油！！！fighting fighting fighting!!!