日期:2019-06-19

晚自习

关键词:状态压缩,基础,位运算

引例

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

解析

数学解法

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

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

$n!$为$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;
}
Last modification:June 19th, 2019 at 09:13 pm
如果您觉得我的文章有用,请赏一颗糖糖。