第一次没认真听，没听懂。（有点难）
第二次才搞懂，主要位运算太烦了！！！
位运算基础知识：
|
名称 |
符号 |
规则 |
|
按位与 |
& |
全一则一，否则为零 |
|
按位或 |
| |
有一则一，否则为零 |
|
按位取反 |
~ |
是零则一，是一则零 |
|
按位异或 |
^ |
不同则一，相同则零 |
|
移位 |
>>和<< |
向右、向左移位 |
集合取并：A|B
集合取交：A&B
集合相减：A&~B
集合取反：^A
置位
A |= 1 << bit
清位
A &= ~(1 << bit)
测位
(A & (1 << bit)) != 0
(A >> bit & 1) != 0
其它运算
取最后一个非0位(Extracting every last bit)
A & -A
A & ~(A-1)
统计非0位(Counting out the bits)
For (; A; A -= A & -A) ++cnt;
取所有子集(All the subsets)
X = A
While (X) X = (X - 1) & A
还有些运算
判断是否有相邻的1
(A & A>>1) == 0
交换两整数
a ^= b, b ^= a, a ^= b
还有很多很多……（多练就会了）
我们知道，用DP解决一个问题的时候很重要的一环就是状态的表示，一般来说，一个数组即可保存状态。
但是有这样的一些题目，它们具有DP问题的特性，但是状态中所包含的信息过多，如果要用数组来保存状态的话需要四维以上的数组。
于是，我们就需要通过状态压缩来保存状态，而使用状态压缩来保存状态的DP就叫做状态压缩DP。
如0=00000（2）,1=00001（2），00001就是一种状态。
2=00010（2），3=00011（2），4=00100（2）……31=11111(2)
所以0-31就是五个点的状态
合法布阵问题
P1879 [USACO06NOV]玉米田Corn Fields
题意：给出一个n行m列的草地(n,m<=12)，1表示肥沃，0表示贫瘠，现在要把一些牛放在肥沃的草地上，但是要求所有牛不能相邻，问你有多少种放法。
分析：假如我们知道每行都有x种合法放法（也就是x种状态），所以对于第i行就有x种放法，那么对于第i+1行的每种放法就有对应的x种放法。
所以定义dp[i][j]表示第i行状态为j时的方法数(j=0,j<=x;j++)，有转移方程：dp[i][j]=sum(dp[i-1][k]) k表示i-1行的状态(k=0,k<=x;k++)。
然而，动归方程想出来了还远远不够……/*orz_wa*/
1、预处理第i行的草地map[i]，用一个二进制数表示，1表示不能放，0表示可以放。如map[1]=15,转成二进制数就是01111，就说明是 放，不放，不放，不放，不放。二进制的神奇！！！
（常理应该是1能放 0不能放，具体原因等下就知道了，主要是方便位运算）。
2、预处理第i行符合条件（不相邻）的状态st[i]，每行共有(1<<m)-1种状态（一个点2种，二个点4种，三个点8种……）。（i=1;i<=(1<<m)-1;i++）
但是很多是相邻的，怎么判断某一状态是否相邻：i&(i<<1)
3、怎么处理肥沃贫瘠问题呢，对于第i行的地形map[i]和某一状态st[k]，如果map[i]&st[k]>=1（如map[2]=10010,st[2]=01110,那么map[2]&st[2]=00010=2>1,所以重复了，关键：同1为1，否则为0）即说明出现了放到贫瘠草地的情况
4、对于第i行不和i-1行相邻，st[i]&st[i-1]>=1，同上（3）即不满足（转换为st[i]&st[i-1]==0），st[i]是第i行的状态，st[i-1]是i-1行的状态
代码：
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int mod=100000000; int n,m; int st[1<<12],map[1<<12];//分别表示每一行的状态和草地的状态 int dp[15][1<<12]; int main() { scanf("%d%d",&n,&m); int x; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&x); if(x==0)map[i]=map[i]|(1<<j-1); } int k=0; for(int i=0;i<=(1<<m)-1;i++)//计算每行合法的放置方式 { if(!(i&(i<<1)))st[++k]=i; } for(int i=1;i<=k;i++)//特判第一行 { if(!(st[i]&map[1]))dp[1][i]=1; } for(int i=2;i<=n;i++) //列举每一行（除了第一行） { for(int j=1;j<=k;j++) //每行可能情况 { if(!(map[i]&st[j])) //符合土地肥沃贫瘠 for(int r=1;r<=k;r++) //i-1行的情况 { if(!(map[i-1]&st[r])) // i-1行r状态符合土地肥沃贫瘠 { if(!(st[j]&st[r])) // i行j状态和i-1行r状态是否相邻 dp[i][j]+=dp[i-1][r]; //加方案数量 } } } } int ans=0; for(int i=1;i<=k;i++) { ans=(ans+dp[n][i])%mod; //答案？？ } printf("%d",ans); return 0; }
总结：确定状态，从一维转向二维……（做多了就有经验，from_Mr.Li）
此题意思很简单,就是十字架上的不能有两个点放炮兵。
分析：
而m即一行的个数小于等于10，每个格子上只有防或不放两种情况
很自然就会想到状压DP
还有一点很重要：
要符合题目条件的 只有平原可以放炮兵。
所以还要匹配 炮兵放法与平原 的关系（一共要判断3种，PH，列列列，横横横）。
如下是DP思考过程：（和玉米田差不多）
我们需要考虑定义，我们可以定义dp[i][j][k]表示到第i行状态为j,且上一行状态为k时的最大方案数
然后我们要来考虑初始化，因为状态肯定由前两行推过来，所以我们需要单独处理第一二行的方案数
取最大的话就一定要和 原来的自己、前一个状态+增长 比较，取较大的那个
最后还有一个问题，数组dp[105][1024][1024]!!!!这空间超400MB啊！
所以还得优化空间。
滚动数组:因为当前状态只与前两行有关，所以只需保留有用的三行
dp[105][1024][1024] --> dp[3][1024][1024] 好很多了（已经不爆了，但我们要做到最优，这是OIer的信念）
预处理:实际上没有几种情况是可以满足横排的（m = 10时，70个不到），于是我们就可以把这些满足条件的保存下来。~~~
dp[3][1024][1024] --> dp[3][70][70]
代码：
#include<cstdio> #include<iostream> using namespace std; const int maxn=101; int n,m; int st[70],sum[70]; int cnt; int dp[3][70][70]; int map[maxn]; int ans=0; void init(int s,int tot,int i) { if(i>=m) { st[++cnt]=s; sum[cnt]=tot; //printf("st=%d sum=%d ",st[cnt],sum[cnt]); return; } init(s,tot,i+1); init(s+(1<<i),tot+1,i+3); } void add() { for(int i=1;i<=cnt;i++) { //printf("st=%d map=%d ",st[i],map[0]); if(!(map[1]&st[i])) { dp[1][i][0]=sum[i]; //printf("%d ",dp[1][i][0]); } //printf("sum=%d %d ",sum[i],dp[0][i][0]); } for (int i=1;i<=cnt;i++) { if(!(st[i]&map[2])) for (int j=1;j<=cnt;j++) if((!(st[j]&map[1]))&&(!(st[i]&st[j]))) { dp[2][i][j]=sum[i]+sum[j]; //printf("i=%d j=%d %d ",st[i],st[j],dp[2][i][j]); } } } void come_dp() { for (int i=3;i<=n;i++) { for (int j=1;j<=cnt;j++) { if(!(st[j]&map[i])) for (int k=1;k<=cnt;k++) if((!(st[k]&map[i-1]))&&(!(st[k]&st[j]))) { for (int u=1;u<=cnt;u++) if((!(st[u]&map[i-2]))&&(!(st[u]&st[j]))&&(!(st[u]&st[k]))) dp[i%3][j][k]=max(dp[i%3][j][k],dp[(i-1)%3][k][u]+sum[j]); } } } } void work() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { char x; cin>>x; map[i]<<=1; if(x=='H') map[i]+=1; } } //printf("%d ",map[1]); init(0,0,0); add(); come_dp(); for (int i=1;i<=cnt;i++) for (int j=1;j<=cnt;j++) ans=max(ans,dp[n%3][i][j]); printf("%d",ans); } int main() { work(); return 0; }
其实状压DP不过就是将一个状态转化成一个数，然后用位运算进行状态的处理。理解了这一点，其实就跟普通的DP没有什么两样了。