状压dp学习笔记

前置

各种位运算

& 与 两个都为1时返回1

? 1&1=1, 1&0=0, 0&1=0, 0&0=0

| 或 有一个为1时返回1

? 1|1 = 1, 1|0 = 1, 0|1 = 1, 0|0 = 0

^ 异或 相同为0 不同为1

? 1^1=0, 1^0=1, 0^1=1, 0^0=0

~ 非 1变0 0变1

? ~1 = 0, ~0 = 1

? ~(10001) = 01110

<< 左移

? 相当于乘2

>> 右移

? 相当于除2

状压dp

板子(P1879 [USACO06NOV]玉米田Corn Fields)

\[ f[i][j] = (f[i][j] + f[i - 1][k])\pmod p \]

#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 100010
const int mod = 1e8;

using namespace std;

int n, m, t, tot, ans, state[maxn], dp[20][maxn], no[maxn];
//state表示所有状态，no表示不能种草的土地，dp[i][j]表示前i行 状态为j时的最大方案数
void init()
{
    for(int i = 0; i < 1 << m; i++)
        if((i & (i << 1))== 0)//如果将一个数左移1位后与上它本身等于0，则说明这个数的二进制表示里的1不相邻（合法），自己写一下就能得出
            state[++tot] = i;//比1 << m 小的所有数的二进制表示可以表示出所有的可能的合法状态
}

int main() {
    scanf("%d%d", &n, &m);
    init();//初始化
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            scanf("%d", &t);
            if(!t) 
            {
                no[i]|=1<<j;//调试一下会好懂，即如果t是0（不能种草）则将那一位变成1，利用了或运算
            }
        }
    }
    dp[0][1] = 1;//第0行不能放，但不放也是一种状态，所以为1
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= tot; j++)//当前行的状态
        {
            if(no[i] & state[j]) continue;//不能种在差土地上
            for(int k = 1; k <= tot; k++)//上一行的状态
            {
                if(state[j] & state[k]) continue;//这一行和上一行不能有边相邻的土地种草
                dp[i][j] += (dp[i - 1][k] % mod);
            }
        }
    for(int i = 1; i <= tot; i++)
    {
        ans += dp[n][i];
        ans %= mod;
    }
    printf("%d", ans);
    return 0;
}

其实就是用二进制优美的暴力枚举

题目

P1896 [SCOI2005]互不侵犯

#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 100010 
typedef int int_;
#define int long long

using namespace std;

int n, k, state[maxn], dp[11][maxn >> 1][83], tot, king[maxn];
int ans;

void init()
{
    for(int i = 0; i < 1 << n; i++)
        if((i & (i << 1)) == 0) 
        {
            state[++tot] = i;
            int t = i;
            while(t)
            {
                king[tot] += t % 2;
                t >>= 1; 
            }
        }
}

int_ main() {
    scanf("%lld%lld", &n, &k);
    init();
    for(int i = 1; i <= tot; i++)
        if(king[i] <= k) dp[1][i][king[i]] = 1;
    for(int i = 2; i <= n; i++)
        for(int j = 1; j <= tot; j++)
        {
            for(int p = 1; p <= tot; p++)
            {
                if(state[p] & state[j]) continue;
                if(state[p] & state[j] >> 1) continue;
                if(state[p] & state[j] << 1)continue;
                for(int l = 1; l <= k; l++)
                {
                    if(king[j] + l > k) continue;
                    dp[i][j][king[j] + l] += dp[i - 1][p][l];
                }
            }
        }
    for(int j = 1; j <= n; j++)
        for(int i = 1; i <= tot; i++)
            ans += dp[j][i][k];
    printf("%lld", ans);
    return 0;
} 

本体要在dp多开一维作为当前国王数量

要注意国王可以吃周围8个格子，所以要注意状态的处理

预处理第一行dp方便

要开long long

P2704 [NOI2001]炮兵阵地

#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 100010

using namespace std;

int n, m, ans, tot, state[maxn], dp[105][62][62], man[maxn], no[maxn];

void init()
{
    for(int i = 0; i < 1 << m; i++)
    {
        if((i & (i << 2)) == 0 && (i & (i << 1)) == 0)
        {
            state[++tot] = i;
            int t = i;
            while(t)
            {
                man[tot] += t % 2;
                t >>= 1;
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    init();
    for(int i = 1; i <= n; i++)
    {
        scanf("\n");
        for(int j = 0; j < m; j++)
        {
            char t;
            scanf("%c", &t);
            if(t == 'H')
            {
                no[i] |= 1 << j;
            }
        }
    }
    for(int i = 1; i <= tot; i++)
    {
        if(state[i] & no[1]) continue;
            dp[1][i][0] = man[i];
    }
    for(int j = 1; j <= tot; j++)
    {
        if(state[j] & no[2]) continue;
        for(int k = 1; k <= tot; k++)
        {
            if(state[j] & no[2] || state[k] & no[1]) continue;
            if(state[j] & state[k]) continue;
            dp[2][j][k] = dp[1][k][0] + man[j];
        }
    }
    for(int i = 3; i <= n; i++)
    {
        for(int j = 1; j <= tot; j++)
        {
            if(state[j] & no[i]) continue;
            for(int k = 1; k <= tot; k++)
            {
                if(state[j] & state[k] || state[k] & no[i - 1]) continue;
                for(int l = 1; l <= tot; l++)
                {
                    if(state[j] & state[l] || state[k] & state[l]) continue;
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][k][l] + man[j]);
                    ans = max(ans, dp[i][j][k]);
                }
            }
        }
    }
    printf("%d", ans);
    return 0;
}

这道题其实也是要注意炮兵攻击范围，这个范围不但会影响当前层和下一层，还会影响下下层

所以我们多开一维作为上上层的状态，同时dp时多进行一次循环

要预处理前两层

注意init()处理所有状态时要保留当前层一个炮兵都不放的状态

状压dp学习笔记

原文：https://www.cnblogs.com/wyswyz/p/11273607.html