状压DP
[SCOI2005] 互不侵犯
点击查看题面
题目描述
在 \(N \times N\) 的棋盘里面放 \(K\) 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 \(8\) 个格子。
输入格式
只有一行，包含两个数 \(N,K\)。
输出格式
所得的方案数
样例 #1
样例输入 #1
3 2
样例输出 #1
16
提示
数据范围及约定
对于全部数据，\(1 \le N \le 9\)，\(0 \le K \le N\times N\)。
\(\text{upd 2018.4.25}\)：数据有加强。
优化
可以发现，这道题超时的原因是枚举的没用状态太多了，所以说只要我们去掉这些状态那么时间复杂度就是最优的了。
首先可以想到的就是\(dp\)，\(dp\)的本质就是优化\(dfs\)。可以发现当前这一行的状态是需要用放到\(dp\)状态里，又不可能把添加\(n\)维表示当前点是否放了国王。可以发现如果把这\(n\)维合并成\(1\)维，这个合共其实可以把一个二进制当成当前的状态比如说\(10010_2\)表示从左到右第\(1\)位有一个国王，第\(4\)位也有一个国王。这个技巧就被称为状态压缩，状态压缩之后的操作可以使用位运算来解决。下图是一张关于位运算的表格：
| << | 二进制左移 |
|---|---|
| >> | 二进制右移 |
| & | 两个二进制每一位只要是\(0\)那么结果中这一位就是\(0\) |
| ^ | 相同为\(0\)，不同为\(1\) |
| | | 两个二进制每一位只要是\(0\)那么结果中这一位就是\(0\) |
回到这一题那么我们的状态就可以设成\(f_{i,j,k}\)表示在第\(i\)行中，状态为\(j\)，放置了\(k\)个国王的方案数
好，我们现在就要写出这一题的转移方程，因为国王的攻击范围涉及到上一行所以我们需要找到上一行，因此我们就要把上一行的状态也放进当前状态里。所以状态方程就应该是:
\[dp_{i,j,l}+=dp_{i-1,x,l-num_j}; \]\(i\)是行数，\(j\)是这一行的状态，\(x\)是上一行的状态，\(l\)是这一行和上一行选择的国王数，\(num_i\)表示第i个状态的国王数。
那么该怎么求道第\(i\)行的国王数和状态的？？
其实这个问题是对于一行上的，那么就可以用\(dfs\)来枚举每一个状态即可。
实现过程：
void dfs(int x, int sum, int cur) {
if (cur >= n) {
sta[++cnt] = x;
num[cnt]=sum;
return;
}
dfs(x,sum,cur+1);
dfs(x+(1<<cur),sum+1,cur+2);
}
那么最终的答案就应该是对于最后一行一种状态放置所有国王的方案综合也就是：
\[\sum_{i是状态}{dp_{n,i,k}} \]最终代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=10;
int sta[1<<N],num[1<<N],cnt,n,k,ans;
int dp[N][1<<N][N*N];
void dfs(int x, int sum, int cur) {
if (cur >= n) {sta[++cnt] = x,num[cnt]=sum;return;}
dfs(x,sum,cur+1),dfs(x+(1<<cur),sum+1,cur+2);
}
bool check(int i,int j){return !(sta[i]&sta[j]||(sta[i]<<1)&sta[j]||sta[i]&(sta[j]<<1));}
signed main(){
cin>>n>>k;
dfs(0,0,0);
for(int i=1;i<=cnt;i++)dp[1][i][num[i]]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<=cnt;j++)
for(int x=1;x<=cnt;x++){
if(!check(j,x))continue;
for(int l=num[j];l<=k;l++)dp[i][j][l]+=dp[i-1][x][l-num[j]];
}
for(int i=1;i<=cnt;i++)ans+=dp[n][i][k];
return cout<<ans,0;
}