动态规划---状压dp

状压dp，就是把动态规划之中的一个个状态用二进制表示，主要运用位运算。

这里有一道例题：蓝书P639猛兽军团1 [SCOI2005]互不侵犯

题目：

题目描述

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

注：数据有加强（2018/4/25）
输入输出格式
输入格式：

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

输出格式：

所得的方案数

输入输出样例
输入样例#1： 复制

3 2

输出样例#1： 复制

16

直接上代码，注释很详细

#include<cstdio>
#include<iostream>
#include<cstring>
#define N 15
#define M 110
#define MAX 550
using namespace std;
/*
见蓝书641页
*/
int s[MAX]; // 记录一行可能的状态
int num[MAX]; //s数组对应每个状态放了多少个猛兽
int states;
long long f[N][M][MAX]; //f[i][j][k]第i行状态为k，放了j个猛兽
int n,m;
void init_state() //预处理s,num数组，代表一行之内所有的可能性
{
    states = 0;
    for(int i = 0; i < (1 << n); i++) //注意，这里是枚举状态
    {
        if(i & (i << 1)) //处理一排上的冲突情况
            continue;
        int t = i;
        num[states] = 0;
        while(t)
        {
            num[states] += (t & 1);
            t = t >> 1;
        }
        s[states++] = i;  //保存状态
    }
}
void dp()
{
    int a,c,mm,b,cc;
    long long ans;
    memset(f,0,sizeof(f));
    //单独算第一行和最后一行
    for(int i = 0; i < states; i++)
    {
        int j = num[i];
        if(j <= m)  //不能超过总数
            f[1][j][i]++;
    }
    for(int i = 2; i < n; i++) //2~n - 1行
    {
        for(int j = 0; j <= m; j++) // 到第i行，一共放了j个猛兽
        {
            for(a = 0; a < states; a++) //i行状态
            {
                c = num[a];
                if(c > j)
                    continue;
                mm = j - c;//前i - 1行的总数
                for(int b = 0; b < states; b++) //枚举i-1行
                {
                    cc = num[b];
                    if(cc > mm)
                        continue;
                    if(s[a] & s[b]) //上下有攻击
                        continue;
                    if(s[a] & (s[b] << 1)) //对角有攻击
                        continue;
                    if(s[b] & s[a] << 1) // 同上
                        continue;
                    f[i][j][a] += f[i - 1][mm][b];
                }
            }
        }
    }
    ans = 0;
    for(a = 0; a < states; a++) //最后一行
    {
        c = num[a];
        if(c > m)
            continue;
        int j = m - c;
        for(int b = 0; b < states; b++) //枚举n-1行
        {
            cc = num[b];
            if(cc > j)
                continue;
            if(s[a] & s[b]) //上下有攻击
                continue;
            if(s[a] & (s[b] << 1)) //对角有攻击
                continue;
            if(s[b] & s[a] << 1) // 同上
                continue;
            f[n][m][a] += f[n - 1][j][b];
        }
        ans += f[n][m][a];
    }
    printf("%lld\n",ans);
}
int main()
{
    scanf("%d%d",&n,&m);
    init_state();
    dp();
    return 0;
}

上面这个代码过于复杂，不好理解，我们换一种写法：

#include<bits/stdc++.h>
using namespace std;
const int M=1<<9;
long long g[M],h[M],f[10][M][82],n,k,tot=0;
int main()
{
    cin>>n>>k;
    memset(f,0,sizeof(f));
    for(int x=0; x < (1<<n); x++) //第一排单独处理 
    {
        if(!(x & (x>>1)) && !(x&(x<<1)))g[x] = 1;//处理g数组,同一排左右不矛盾 
        int w = x;
        while(w)
        {
            if(w % 2)h[x]++;
            w /= 2;
        }
        if(g[x])
        f[1][x][h[x]] = 1;
    }
    for(int x = 2; x <= n; x++)
    {
        for(int y = 0; y < (1<<n); y++)
        {
            if(g[y])
            {
                for(int z = 0; z < (1<<n); z++)
                {
                    if(g[z] && !(y&z) && !(y & (z>>1)) && !(y&(z<<1))) //只用考虑该排与上一排 
                    {
                        for(int w = 0; w + h[z] <= k; w++)
                        f[x][z][w + h[z]] += f[x - 1][y][w]; //w枚举总共放的国王的个数
                    }
                }
            }
        }
    }
    for(int y=0; y<(1<<n); y++)tot+=f[n][y][k];
    cout<<tot;
    return 0;
}

动态规划---状压dp

推荐阅读