日期：2019-06-19

晚自习

关键词：状态压缩，基础，位运算

引例

在$n*n (n≤20)$ 的方格棋盘上放置$n$个车(可以攻击所在行、列)，求使它们不能互相攻击的方案总数。

解析

数学解法

每一行均有且只有1个车，从上向下依次每行放置，用$i$表示行号，则第$i$行有$n+1-i$种方法放置。

故总的放置方法$ans$为：$$ans=\prod_{i=1}^{n} n+1-i=n!$$

代码如下：

#include <bits/stdc++.h> 
using namespace std;
int main(){
    int ans=1;
    cin>>n;
    for(int i=1;i<=n;i++){
        ans*=i;
    }
    cout<<ans<<endl;
    return 0;
}

状态压缩递推解法

一个int表示一种搜索状态。

每一行均有且只有1个车，故第$i$行是否已经放置车可以用这个状态所对应的这个int的二进制码的从左向右第i位表示。

故本质是求$$f_x = \sum_{i=1}^n {f_{s-2^i}}$$

其中$f_0=1$

代码如下：

#include <bits/stdc++.h> 
using namespace std;
int f[10485796]={0},n;
int main(){
    cin>>n;
    f[0]=1;
    for(int i=1;i<1<<n;i++){//caculate f[i]
        for(int j=i;j>0;j-=(j&-j)){
            f[i]+=f[i^(j&-j)];
        }
    }
    cout<<f[(1<<n)-1]<<endl;
    return 0;
}

版权声明：本文是原创文章，版权归 星雾月雨 所有。

本文链接：https://www.ariels.xyz/archives/202.html

本站所有下方标记为「允许规范转载」的原创文章均采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。
您可以自由地转载，但请务必注明文章来源且不可用于商业目的。