状压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("
");
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()处理所有状态时要保留当前层一个炮兵都不放的状态