题解 P1896 【[SCOI2005]互不侵犯】
Ykimna
2019-10-26 11:25:32
### 需要强调一点：状压dp也是 **dp**,需要普通动态规划基础，如没有普通动态规划基础还是先去巩固基础更为重要。
我也不知道我是否能讲清楚，如果哪里有疑问可以评论，或私信我（我在退役之前都能回答你）
------------
### 前置知识：普通动态规划，位运算。
这道题题意非常简单就不再赘述，直接来讲讲数据处理方法。
如果一般的动态规划去想这道题，你会发现它的状态很难去表示和转移（ ~~当然你也可以去开个10维数组~~ ），这就需要引入一种方法去表示它的状态，我们可以用一个数来表示它的状态，这个数每位只有两个数0或1，对于这道题来说1为国王，0为空格。
比如：10101 表示的就是：
很显然如果棋盘有9格那么这个数会到1e8数组会炸，所以我们就需要用个方法来减维，那就是 **状压** 。因为这个数每位只0或1，那么很显然我们可以用二进制来表达这个状态，再把这个二进制转化为十进制来存储，1e8就就会退化为 $\log_21e8$ 最大也就为 $2^9-1(511)$ 。这样就可以用数组存下了。
接下来就来讲一下思路：我们先来处理每一行棋盘的所有合法状态。根据题意每个国王的左右不能有国王也就是只能插空站，在判断国王是否相邻（状态是否合法）有一种简单的方法 **&** 运算。这里举两个例子。
1. 10101
我先把这个数左移一位再与这个数进行 **&** 运算
2. 11010
我们发现合法序列的在计算后的值为 $0$ ，而不合法的序列计算后的值不为 $0$ 。因此我们就可一从0枚举到 $2^n-1$ 把所有的合法序列存在 $sta[N]$ 数组里面。同时我们可以用 $king[N]$ 数组把每一个合法状态有多少个国王存下来。
代码如下：
```cpp
int cnt=0;
for(int i=0;i<=(1<<n)-1;i++)
{
if(i&(i<<1)) continue;
sta[++cnt]=i;int gw=i; //存合法状态
while(gw>0)//计算国王数量
{
if(gw%2==1) king[cnt]++;
gw>>=1;
}
}
```
之后的大致思路就是比较所有 $X$ 行和 $Y$ 行，其中 $X$ 为 $Y$ 的上一行，也就是说 $X=Y-1$ ，枚举所有 $X$ 行和 $Y$ 行的所有合法状态再计算出这 **两排** 的合法状态，因为想要整个棋盘合法，就要每一行棋盘都要与其上下两行棋盘合法
也就是国王的上方，左上，右上和下方，左下，右下都不能为国王。比较方法如下：
```cpp
if(sta[j]&sta[k]) continue;//j枚举的是Y行的合法状态，k为X行的合法状态
if((sta[j]<<1)&sta[k]) continue;
if(sta[j]&(sta[k]<<1)) continue;
```
判断合法的状态都讲了，就可开始$dp$了，我们定义一个$dp[i][j][k]$数组，前i行，状态为j，使用了k个国王时的总方案数。再前文枚举$X$和$Y$合法后，我们就再枚举国王数就可以了。代码如下
```cpp
for(int c=0;c<=ki;c++)
{
if(king[j]+c>ki) break;
dp[i][j][king[j]+c]+=dp[i-1][k][c];
}
```
### 细节：处理好位运算的优先级，还有就是 ~~十年OI一场空，不开long long见祖宗~~
下面贴完整代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=(1<<10)+20;
const int M=17;
int n,ki,cnt,king[N];
long long ans,sta[N],dp[M][N][M*M];
int main()
{
cin>>n>>ki;
for(int i=0;i<=(1<<n)-1;i++)
{
if(i&(i<<1)) continue;
sta[++cnt]=i;int gw=i; //存合法状态
while(gw>0)//计算国王数量
{
if(gw%2==1) king[cnt]++;
gw>>=1;
}
}
for(int i=1;i<=cnt;i++)//初始化第一排，因为我们枚举的是X与X-1行
if(king[i]<=ki) //一行的国王数不可能超过国王的总数量
dp[1][i][king[i]]=1;
for(int i=2;i<=n;i++)//枚举每行
{
for(int j=1;j<=cnt;j++)//X行的合法状态
{
for(int k=1;k<=cnt;k++)//X-1（Y）行的合法状态
{
if(sta[j]&sta[k]) continue;
if((sta[j]<<1)&sta[k]) continue;
if(sta[j]&(sta[k]<<1)) continue;
for(int c=0;c<=ki;c++)//国王数
{
if(king[j]+c>ki) break;
dp[i][j][king[j]+c]+=dp[i-1][k][c];
}
}
}
}
for(int i=1;i<=cnt;i++)//因为记录的是前i行,所以加上在前n行的所有合法状态
ans+=dp[n][i][ki];
cout<<ans<<endl;
return 0;
}
```
~~码字不易，反正不要钱多少赞一个~~