状压dp
就是把状态压缩的dp
这样还是一种暴力但相对于纯暴力还是优雅的多。
实际上dp就是经过优化的暴力罢了
首先要了解位运算
给个链接吧
[https://blog.****.net/u013377068/article/details/81028453]
一些例题
之所以很难理解是因为没搞懂那些位运算的特点
在接下来的代码中会讲
poj 2411
[http://poj.org/problem?id=2411]
就是给你一个mn的网格，有两种砖12和2*1；
问你刚好填满的方案有多少
分析
首先你放置的时候会受到前一列影响，当前的放置也会队下一列有影响
假设你要放的位置有了就不能放了，再往下一行放
如果该位置没有就可以放一个12的，但它会对下一列有影响所以你得记录产生的影响
如果该位置没有且它下面也没有被占用就可以放一个21
之后你得跳到i+2行去放了 i是当前行
代码里说了很多关键的东西自己看吧
代码
#include<iostream>
#include<string.h>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
ll dp[15][2200];
int n,m;
//dp[i][j]//表示第i列状态为j时的方案数
void dfs(int i,int j,int state,int next){
//i表示行,j表示列,state表示当前状态,next表示到达下一列的状态
if(i==n){
//当前列已经到达第n+1行了
//下面有说 i是表示第i+1行的
dp[j+1][next]+=dp[j][state];
return;
}
else{
//如果当前列的当前行被占用过了往下一行搜索
if((state&(1<<i))){
//特别注意i是表示第i+1行的状态不是i行
//因为本来1在做好一位左移了i位它的位置在第i+1了，右边数起
dfs(i+1,j,state,next);
}
//如果当前格子没被占就可以放一个1*2,下一列就会改变状态
if((state&(1<<i))==0)
dfs(i+1,j,state,next|(1<<i));
//如果当前格子和下一行的格子都不被占用就可以放一个2*1下一列不会改变状态
//还得判断是否超出最下面那行
if(i+1<n&&(state&(1<<i))==0&&(state&(1<<(i+1)))==0)
dfs(i+2,j,state,next);
}
}
int main(){
//freopen("in.txt","r",stdin);
while(~scanf("%d%d",&n,&m)&&(n+m)){
if(n>m) swap(n,m);
memset(dp,0,sizeof(dp));
dp[1][0]=1;
for(int i=1;i<=m;i++)
for(int j=0;j<(1<<n);j++)
if(dp[i][j]>0) dfs(0,i,j,0);//如果有某种状态转移到该状态才会进行填充
//第m列刚好填充满而且第m+1列是没有的才是答案
printf("%lld\n",dp[m+1][0]);
}
return 0;
}
poj 3254
[http://poj.org/problem?id=3254]
题意就是给你
一个矩阵 某个位置是0不可以种，1可以种
而且相邻的不能种也就是上下左右不能种
为你有多少种 种法
分析
对于某个位置该不该种你得看你左边和上边，因为我们是从第一列往右1列1列地选择种的方式不用考虑下面和左边
每一列的状态比如5=（101）表示该列的第一行和第三行都已经种了玉米，第二行没种
最后定义状态和转移方程
dp[i][j]表示第i列状态为j的方案数
dfs(int i,int j,int state,int next,bool flag)
//参数分别是行 列 状态 下一列状态 上一行是否种玉米
结果就是最后列所以状态之和
代码
#include<iostream>
#include<algorithm>
#include<string.h>
#include<cstdio>
using namespace std;
const int N=(1<<12)+10;
const int mod=1e8;
int a[20][20],dp[20][N];
//dp[i][j]表示第i列状态为j的方案数
int n,m;
void dfs(int i,int j,int state,int next,bool flag){
//参数分别是行 列 状态 下一列状态 上一行是否种玉米
//一定注意“”i表示的是第i+1行
if(i==n){
dp[j+1][next]=(dp[j+1][next]+dp[j][state])%mod;
return;
}
else{
//可以种,(i,j)这个位置为1，因为i表示的是第i+1行
//而实际中他的位置是a[i+1][j];
if(a[i+1][j]==1&&(state&(1<<i))==0&&flag==0){
//有两种选择种或者不种
dfs(i+1,j,state,next|(1<<i),1);
dfs(i+1,j,state,next,0);
}
else dfs(i+1,j,state,next,0);
}
}
int main(){
freopen("in.txt","r",stdin);
while(~scanf("%d%d",&n,&m)){
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
memset(dp,0,sizeof(dp));
dp[1][0]=1;
for(int i=1;i<=m;i++)
for(int j=0;j<(1<<n);j++)
if(dp[i][j]>0)
dfs(0,i,j,0,0);
int sum=0;
for(int i=0;i<(1<<n);i++)
if(dp[m+1][i]>0)
sum=(sum+dp[m+1][i])%mod;
printf("%d\n",sum);
}
return 0;
}