洛谷 P1896 [SCOI2005]互不侵犯（状压dp）
洛谷 P1896 [SCOI2005]互不侵犯（状压dp）
P1896 [SCOI2005]互不侵犯
题目描述
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。
注：数据有加强（2018/4/25）
输入格式
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
输出格式
所得的方案数
输入输出样例
输入 #1
3 2输出 #1
16思路：状压dp，
首先 先解释一下状压是什么吧 对于这种类型的题 每个点 都只存在两种情况 即为放了东西 没放东西 （这里先解释一下为什么不可以把状态设为每一个点 因为 如果设为每一个点的话 状态很不好转移 下一个点的位置无法确定）那么 我们就可以把放了东西定为1 没放东西定为0 于是 我们便可以得到类似“0 1 0 1”这样的一个状态（这里我们只模拟了一行的状态） 而这样的一个状态“0 1 0 1” 可以把他看作一个二进制数 我们也就可以很轻松的把他转换为一个10进制数 即5 那么 这个十进制数5 就可以表示这样的一个“0 1 0 1”的状态 也就是说 我们把这样的一个状态压缩到了一个十进制数里面 也就是状态压缩了
而我们的DP 就是通过状态的转移来进行计算 那么我们这个时候 所需要存储的状态 就会变成一个数 避免了原先一整行的摆放情况难以存储的问题
于是我们看回这道题 首先 它就是刚刚讲过的 是一个判断摆放情况的题 而且 他的数据范围很小（数据范围大了 状压就不一定能做了 因为它有一个进制的转换） 所以 可以判断出来 这是一道状压DP
那么 我们就可以设状态为每一行的摆放情况 f(i,j,k) 用来表示 第i行 摆放情况为j 截止当前行 使当前状态下一共摆放的个数为k的情况总数
那么 他的状态怎么转移呢 因为它本质上是一个放或不放的题 所以他的动态转移方程类似于01背包
即
那么我们只需要枚举行 枚举该行状态 枚举上一行状态 再判断一下两状态是否冲突 然后再统计答案就好啦
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register ll
#define inf 2147483647
#define lb(x) (x&(-x))
ll sz[200005],n,k1;
template <typename T> inline void read(T& x)
{
x=0;char ch=getchar();ll f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}x*=f;
}
inline ll query(ll x){ll res=0;while(x){res+=sz[x];x-=lb(x);}return res;}
inline void add(ll x,ll val){while(x<=n){sz[x]+=val;x+=lb(x);}}//第x个加上val
ll dp[10][1000][20],cost[1000],sit[1000],cnt;//sit[i]为第i种状态的二进制表示，cost[i]表示第i种状态的用1个数
inline void dfs(int state,int sum,int column)
{
if(column>=n)
{
sit[++cnt]=state;
cost[cnt]=sum;
return ;
}
dfs(state,sum,column+1);
dfs(state+(1<<column),sum+1,column+2);
}
int main()
{
cin>>n>>k1;
dfs(0,0,0);
for(int i=1;i<=cnt;i++)dp[1][i][cost[i]]=1;
for(int i=2;i<=n;i++)
{
for(int j=1;j<=cnt;j++)
{
for(int k=1;k<=cnt;k++)
{
if(sit[j]&sit[k])continue;
if(sit[j]&(sit[k]<<1))continue;
if((sit[j]<<1)&sit[k])continue;
for(int m=k1;m>=cost[j];m--)dp[i][j][m]+=dp[i-1][k][m-cost[j]];
}
}
}
ll ans=0;
for(int i=1;i<=cnt;i++)ans+=dp[n][i][k1];
cout<<ans<<endl;
return 0;
}