「SCOI2005」互不侵犯King

发布于 2018-02-09  285 次阅读


在清北学堂DP&Graph班里学到了这一题,状压DP的入门题目

题目描述

题目背景

在N×N的棋盘里面放K个King,使他们互不攻击,共有多少种摆放方案。King能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。

输入输出格式

输入格式:

只有一行,包含两个数N,K $( 1 <=N <=9, 0 <= K <= N * N) $

输出格式:

所得的方案数

样例

样例输入

3 2

样例输出

16

思路

看到这一题,首先就应该想到搜索和DP,显然暴力是不可取的。
则我们考虑DP。
设$ f[i][j][k] $表示到第i行第j列合法时已经摆放了$ k $个King时的方案数。
我们设$ status[i] $来记录一个二进制数来表示状态(第$ j $位为1的时候表示这一列有国王,反之则没有)。
$ cnt[i] $记录第i中情况有多少个1.
DP的话我们可以按照行进行状态压缩,这样即可得到一个状态转移方程:
$$ f[i][l][status[k]] = f[i][l][status[k]] + f[i-1][l-cnt[j]][status[j]] $$

当 $$ status[j] \& status[k] = 0, status[j] \& (status[k] << 1) = 0,status[j] \& status[k] >> 1 = 0 $$
边界情况:$ f[1][cnt[i]][i] = 1 $

代码实现

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------\n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
namespace fastIO{
    #define BUF_SIZE 100000
    #define OUT_SIZE 100000
    #define ll long long
    bool IOerror=0;
    inline char nc(){
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if (p1==pend){
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if (pend==p1){IOerror=1;return -1;}
        }
        return *p1++;
    }
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline void read(int &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    inline void read(ll &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    #undef ll
    #undef OUT_SIZE
    #undef BUF_SIZE
};
using namespace fastIO;

const int MAXN = 9+1;
#define lowbit(x) (x&-x)
int status[(1<<MAXN)+1],cnt[(1<<MAXN)+1],size;
/// status 合法的情况,cnt 情况有多少个二进制1 
LL f[MAXN][MAXN*MAXN][(1<<MAXN)+1];
int N,K;

int main(){
    read(N);read(K);
    int MAX = (1<<N)-1;
    FOR(i,0,MAX){
        if(i & (i>>1)) continue;
        status[++size] = i;
        int x = i;
        while(x){
            x -= lowbit(x);
            cnt[size]++;
        }
    }
    FOR(i,1,size) f[1][cnt[i]][i] = 1;
    FOR(i,2,N){
        FOR(j,1,size){
            FOR(k,1,size){
                if((status[j]&status[k]) || (status[j]&status[k] << 1) || (status[j]&status[k] >> 1)) continue;
                FOR(l,cnt[k],K){
                    f[i][l][k] += f[i-1][l-cnt[k]][j];
                }
            }
        }
    }
    LL ans=0;
    FOR(i,1,size) ans += f[N][K][i];
    printf("%lld\n",ans);
    return 0;
}

一个OIer。