BZOJ - 1087 [SCOI2005]互不侵犯King（状压DP）

传送门：BZOJ - 1087

题目描述

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

输入描述

只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）

输出描述

方案数。

思路分析

一道很经典的状压DP，我也是看了半天题解才懂的。

需要用到三个数组：

• dp[i][j][k]表示第i层状态为j所用棋子总数为k的方案数
• ok[i]表示第i种状态是否合法
• num[i]表示第i种状态需要多少个棋子

状压dp的关键就是各种状态的表示以及位运算

样例输入

3 2

样例输出

16

AC代码

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

#define fi first
#define se second
#define ll long long
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

const int INF = 0x3f3f3f3f;
const int N=10;

ll dp[N][1<<N][N*N],num[1<<N];
bool ok[1<<N];

int main() {
    IOS;
    int n,k;
    cin>>n>>k;
    ll sum=1<<n;
    for(int i=0; i<sum; i++) { //判断每种状态所需要的棋子个数 
        int pos=i;
        while(pos) {
            if(pos&1)num[i]++;
            pos>>=1;
        }
    }
    for(int i=0; i<sum; i++) {
        if(((i<<1)&i)==0)  //判断每种状态是否合法，相邻 
            ok[i]=true;
    }
    for(int i=0; i<sum; i++) {
        if(ok[i]&&num[i]<=k)
            dp[1][i][num[i]]=1; //初始化第一排的dp数组 
    }
    for(int i=2; i<=n; i++) {
        for(int j=0; j<sum; j++) {
            if(ok[j]) {
                for(int s=0; s<sum; s++) {
                    if(j&s)continue;          //判断两种状态是否合法 
                    if((j<<1)&s)continue;
                    if((j>>1)&s)continue;
                    for(int t=k; t>=num[j]; t--)
                        dp[i][j][t]+=dp[i-1][s][t-num[j]];
                }
            }
        }
    }
    ll ans=0;
    for(int i=0; i<sum; i++)
        ans+=dp[n][i][k];
    cout<<ans<<endl;

    return 0;
}