P1896 [SCOI2005]互不侵犯 (状压dp）

[SCOI2005]互不侵犯 - 洛谷

题目描述

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

注：数据有加强（2018/4/25）

输入格式

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

输出格式

所得的方案数

输入输出样例

输入 #1复制

3 2

输出 #1复制

16

题解：

搜索显然是不怎么好过的，那么只能考虑dp。对于这类图中放还是不放，标记类的情况显然可以状压dp。

那么我们首先把每一行所有的可能情况预处理出来，再设dp；考虑从上往下dp，行不能滚动，要开一维；国王数量占一维；还有第j行的状态要占一维；n<=10,看来可行；那么状态转移方程为：

表示前i行，最后一行为j行，国王数量为k的转移。

代码如下：

/*keep on going and never give up*/#includeusing namespace std;#define int long long#define ll long long#define fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);inline int read(){    int x=0,k=1; char c=getchar();    while(c'9'){if(c=='-')k=-1;c=getchar();}    while(c>='0'&&c<='9')x=(x<<3)+(x<=n){s[++cnt]=x;sum[cnt]=num; return ;}dfs(x,num,p+1);dfs(x+(1<<p),num+1,p+2);//对应第p个位置安不安排国王；不安排就往下跳一位，安排之后根据排斥还要多跳一位；}signed main() {n=read(),m=read();dfs(0,0,0);for(int i=1;i<=cnt;i++) dp[1][i][sum[i]]=1;//for(int i=1;i<=cnt;i++) cout<<s[i]<<" "<<sum[i]<<endl;for(int i=2;i<=n;i++){for(int j=1;j<=cnt;j++){for(int k=1;k<=cnt;k++){if(s[j]&s[k]) continue;if((s[j]<>1)&s[k]) continue;for(int z=m;z>=sum[j];z--)  dp[i][j][z]+=dp[i-1][k][z-sum[j]];}}}int ans=0;for(int i=1;i<=cnt;i++) ans+=dp[n][i][m];cout<<ans;}