P7859 [COCI2015-2016#2] GEPPETTO

loverintime · 2021-09-10 20:49:41 · 题解

题意

有 n 个东西，其中 m 对东西不能在一起，问一共有多少种选东西的方案

数据范围

看到数据范围这么小，我们可以想到两种实现方式：爆搜、状压dp

爆搜

爆搜有一个优点：实现简单，并且不会超时。我这里有一个小优化： 记录 s_i 表示与 i 不能一起选的集合，用一个二进制数表示。 搜索时记录现在正在决定选不选的元素 i 和现在不能使用的集合 S ，判断 i 在不在集合中即可判定能不能选， 如果选了 i 就把 S 变成 S\cup s_i

Code

#include<bits/stdc++.h>
using namespace std;
int n,m;
int nset[25];
int ans;
void dfs(int x,int udo){
    if(x==n+1){
        ans++;return;
    }
    dfs(x+1,udo);
    if(!(udo&(1<<x))){
        dfs(x+1,udo|nset[x]);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++){
        int x,y;
        scanf("%d%d",&x,&y);
        nset[x]|=(1<<y);nset[y]|=(1<<x);
    }
    dfs(1,0)
    printf("%d\n",ans);
    return 0;
}

复杂度： \Theta(2^n) （所以数据范围应该增大）

至于状压dp，既然暴力都这么快了，那它还有什么用呢。不过大概说一说思路：

继承之前的做法，记录 s_i 表示与 i 不能一起选的集合，用一个二进制数表示。

复杂度 \Theta(n2^n) 比爆搜还要慢