【BZOJ1087】【SCOI2005】互不侵犯(状压dp)
对于这类棋盘问题 要关注的是这一行与前一行的关系
设dp[i][j][state]表示前i行,已经放了j个国王,状态为state的方案数
然后枚举i,枚举j,再枚举state,再枚举上一行last
先判断state,last各自是否合法,再判断他们俩合起来会不会冲突
最后答案就是最后一行所有状态的方案数之和
我这个写法好像常数巨大啊。。。
#include<bits/stdc++.h>
#define N 10
#define STATE 520
#define ll long long
using namespace std;
int n,k;
ll dp[N][N*N][STATE];
inline bool ok(int state)//判断状态是否合法
{
for(int i=1;i<n;i++) //跳过第1位
{
if(state&(1<<i)) //当前这位是1
{
if(state&(1<<(i-1))||state&(1<<(i+1))) return false;
}
}
return true;
}
inline int popcnt(int x)//二进制下有多少个1
{
int cnt=0;
while(x)
{
if(x&1) cnt++;
x>>=1;
}
return cnt;
}
inline bool conflict(int s1,int s2)
{
if((s1&s2)||(s1&(s2<<1))||(s1&(s2>>1))) return true;
return false;
}
int main()
{
scanf("%d%d",&n,&k);
const int max_state=1<<n;
for(int state=0;state<max_state;state++) if(ok(state)) dp[1][popcnt(state)][state]=1;
for(int i=2;i<=n;i++)
{
for(int j=0;j<=k;j++)
{
for(int state=0;state<max_state;state++)
{
if(!ok(state)) continue;
if(popcnt(state)>j) continue;
for(int last=0;last<max_state;last++)
{
if(conflict(state,last)) continue;
dp[i][j][state]+=dp[i-1][j-popcnt(state)][last];
}
}
}
}
ll ans=0;
for(int i=0;i<max_state;i++) ans+=dp[n][k][i];
cout<<ans;
return 0;
}
转载于:https://www.cnblogs.com/Patrickpwq/articles/9853034.html