P1657 选书 题解

_louhc · 2018-02-18 22:30:05 · 题解

看了这么多题解，竟然没有状态压缩的，所以本蒟蒻来一发。
这里解释一下状态压缩。
把t当做2进制来看，它的第( i + 1 )位就表示第i本书有没有拿走。
比如t = (11010)2表示第1 、 3 、 4本取过了。这里为了方便我不使用第一位
判断时，只要把 t & ( 1 << 编号 ) 就行了，举个例子，t = (11010)2,要判断第3本，1 << 3 = (01000)2,(01000)2 & (11010)2，第4位都是1，所以是true。
取书时，只要把&改成|就行了，请自己分析，这里不再赘述，具体请参照程序。

#include<bits/stdc++.h>
using namespace std;

int n;
int a[25][2];
int ans;
void dfs( int s, int t ){
    if ( s > n ){
        if ( t == ( 1 << ( n + 1 ) ) - 2 )//以防万一
            ans++;
        return;
    }
    if ( ( ( 1 << a[s][0] ) & t ) == 0 )
        dfs( s + 1, ( 1 << a[s][0] ) | t );//简单的搜索
    if ( ( ( 1 << a[s][1] ) & t ) == 0 )
        dfs( s + 1, ( 1 << a[s][1] ) | t ); 
}

int main(){
    scanf( "%d", &n );
    for ( int i = 1; i <= n; ++i )
        scanf( "%d%d", &a[i][0], &a[i][1] );
    if ( n ) dfs( 1, 0 );//是0就不做了，数据太坑，有n = 0的情况，要特判。
    printf( "%d", ans );
    return 0;
}

状态压缩是一种很好的搜索辅助工具，可以减少时间和空间复杂度，很多较难搜索题都可以用到。当然，开数组也行，结果都是一样的，但我偏好于状态压缩。不过，这里事实上用数组会更快更方便，这里我只是从广义上来说的，状压的主要应用还是在记忆化搜索，这里权当做是状态压缩的练习吧。