状态压缩dp
一般来说,状态压缩dp的思路是这样的:
1.枚举第一行所有的状态,构造n位的01串。
2.状态设置:第 \(i\) 行,第 \(i\) 行的状态,第 \(i\) 行0或1的数量。
其他情况自行判断。
3.进行dp计算(一般来说会有许多if)
状压特点:
1.数据范围小。
2.一般来说为什么成立什么不成立,只有两种情况。
3.答案大。
例题:
互不侵犯
题意:对于 \(n\cdot n\) 的图,在上面有 \(k\) 个点,求出这 \(k\) 个点互不成扫雷中的雷的情况数(差不多QAQ)。
我们先来进行分析:
1.只有选或者不选,数据范围小,所以是状压dp。
2.设置状态:\(f[i][j][k]\) 中 \(i为第i行,j为第i行的状态,k为第i行用了几个点\)。
3.建立第一行状态:
if(!(i&(i<<1))) //此时在同一行内不矛盾
完整代码:
int lim=1<<n;
for(int i=1;i<lim;i++){
if(i&(i<<1)) continue;
int k=0;//统计这种状态放置国王的数量
for(int j=0;j<n;j++) if(i&(1<<j)) k++;
s[++s0]=i;//可用状态i,总计可用状态数s0.
num[s0]=k;//每种状态放置国王的数量。
}
然后dp需要枚举上一行和这一行的状态,判断是否成立。
f[0][1][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=s0;j++)
for(int k=0;k<=m;k++)
if(k>=num[j])
for(int t=1;t<=s0;t++)
if(!(s[t]&s[j])&&!(s[t]&(s[j]<<1))&&!(s[t]&(s[j]>>1)))
f[i][j][k]+=f[i-1][t][k-num[j]];
之后再统计一下每一位的答案:
for(int i=1;i<=s0;i++)
ans+=f[n][i][m];//每一种状态进行计算加和
之后输出就好啦:)
© 著作权归作者所有
举报
发表评论
0/200