|
状压这个和二进制分不开关系 所以，对于二进制的熟悉是必不可少的技能 & 与操作，1不变，0变0 | 或操作，0不变，1变1 ^ 异或操作,0不变，1取反 ～ 取反操作，把每一个二进制位0变1，1变0 还有一些复杂操作可以根据这些去理解 状态压缩 所谓状态压缩就是把dp的每一次转移时的状态用二进制来表示 或者用二进制来间接表示 比如 这里有10个苹果，编号1-10 我拿走了1,4,7,9这四个苹果 那么我们可以用011011010这一串二进制数来表示现在的状态 0表示这个位置没有苹果，1表示有 那么这就是一个状态 相比拿一个bool型的数组，这样表示更方便，内存更小，操作更简单 现在我想把拿走的苹果放回去，没拿走的拿走 那么状态就变成100100101 直接取反 a=011011010 b=100100101 a==～b; 这时候就充分展示了状态压缩的快捷性 下面我们讲一道例题。。。。。 在n*n(n≤20)的方格中放置n个车，每个车可以攻击所在的行和列，求方案总数 直接上排列组合，n！，很好理解啊 在n*n(n≤20)的方格棋盘上放置n 个车，某些格子不能放，求使它们不能互相攻击的方案总数。 这时候一些格子不能放，就要考虑每一行的情况 但是 ，，，，即使每一行中有的格子不能放，最终还是每一行每一列都要有一个车子 所以我们用s这个int型的数来表示现在的状态（行状态） 如果这一列现在有车子，那这一位就是1 所以最终s一定会变成11111111111（全是1）只有这样才能把n个车全部放进去 这样这一状态有几个车子说明这就是第几行 那这样转移方程就有了 dp[s]+=dp[s^(s&-s)]; for(;j>0;j-=(j&-j)){ dp[i]+=dp[i^(j&(-j))]; } 还有个问题，有些格子不能放车 这怎么办？？？？？？？？？？？ 还记得前面的苹果吗 用1表示这里能放车子，0表示不可以 在状态转移的时候&一下就可以啦 j=i&s[num]; 代码如下 #include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
long long dp[1<<20];
int s[25];
int main(){
memset(s,0x7fffffff,sizeof(s));
//if(s[1][1]==1)cout<<"sh";
//cout<<(s[1][1]&0)<<endl;
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
s[x]-=(1<<(y-1));
}
dp[0]=1;
for(int i=1;i<(1<<n);i++){
int j,num=0;
for(j=i;j>0;j-=(j&(-j))){
num++;
}
j=i&s[num];
for(;j>0;j-=(j&-j)){
dp[i]+=dp[i^(j&(-j))];
}
}
printf("%lld",dp[(1<<n)-1]);
}
这样基本的状压dp就结束了 也许你已经发现了 所有的n都小于等于20 因为int只有32位 这也是状压的前提 所以当你一直为空间时间复杂度着急时 就去考虑状压 而状压前先找到可以状压的数 就是32位以内的 over |
|
|
