状态压缩DP
一、蒙德里安的梦想
1、思路
当我们把所有的横向小方格放好后，我们竖向放的小方格就只有一种摆放情况
f[i][j]:这里的i是第i列，j存的是当前的第i列的所有小方格的状态，j用二进制表示，每一位代表当前列的每一行小方格的状态，j的范围为0~2^n-1
1是代表在第i-1列的这一行有一个横向的小方块，小方块的末端在i列，我们才记为1。
0一种是没有小方块，一种是横向小方块的前端。
举例说明： k j
第j列： 000010
第k列：100100
同时要满足两个条件
（1）2列之间不能有冲突，即1不能出现在相同位置上，即要满足：(j&k)==0
（2）由于剩下0的位置是要放竖着的小方块，所有我们不能有奇数个0。即满足：j|k
2、代码模板：
#include<iostream>
#include<cstring>
using namespace std;
const int N=12;
const int M=1<<N;
typedef long long ll;
ll f[N][M];//状态方程,i是第i列，j是第i列中小方格的状态，用二进制表示
bool st[M];//记录状态，是否是否是奇数个0
int main()
{
int n,m;//n行，m列
while(cin>>n>>m,n||m)//当有读入时，且n,m不为0时
{
memset(f,0,sizeof f);//将所有初始状态设为0
//接下来预处理操作，对于每种状态，先预处理每列不能有奇数个连续的0
for(int i=0;i<1<<n;i++)//一共n行，即每列有n个格子，1<<n枚举了n个格子的所有情况
{
st[i]=true;//刚开始默认没有奇数个0，即合法情况
int cnt=0;//记连续0的个数
for(int j=0;j<n;j++)//从上到下遍历这一列
{
if(i>>j&1)//当前位的值为1时
{
if(cnt&1)//如果连续0的个数为奇数
st[i]=false;//标记为不合法
cnt=0;
}
else//不为1时
cnt++;
}
if(cnt&1)
st[i]=false;//判断最后的是否合法
}
f[0][0]=1;//
for(int i=1;i<=m;i++)//从0到m列遍历
for(int j=0;j<1<<n;j++)//遍历这一列的每一个状态，1<<n枚举了n个格子的所有情况
for(int k=0;k<1<<n;k++)//遍历上一列的每一个状态，1<<n枚举了n个格子的所有情况
if((j&k)==0&&st[j|k])//如果这两列不冲突且是在一块能有偶数个0
f[i][j]+=f[i-1][k];//那么这种状态下它的方案数等于之前每种k状态数目的和
printf("%ld\n",f[m][0]);
}
return 0;
}
二、最短Hamilton路径
1、思路
2、代码模板：
#include<iostream>
#include<cstring>
using namespace std;
const int N=20;
const int M=1<<N;
int n;
int w[N][N];//记录从ij之间边的权
int f[M][N];//状态方程
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&w[i][j]);
memset(f,0x3f,sizeof f);//初始距离为无穷
f[1][0]=0;//在起点,就算是经过一个点了，距离为0
for(int i=0;i<1<<n;i++)//i存的路径走过的点，1<<n可以把所有情况列出来
for(int j=0;j<n;j++)//遍历n位
if(i>>j&1)//第j位为1，因为走到j了，肯定j位为1才行
for(int k=0;k<n;k++)//遍历j之前的点的所有可能
if(i-(1<<j)>>k&1)//其实可以直接写i>>k&1，就是判断第k位是否是1，是1代表路径过这个点了
f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);//
printf("%d",f[(1<<n)-1][n-1]);
return 0;
}
三、状压+搜索
1、题目3279 -- Fliptile (poj.org)
2、思路
对于这个问题，我们每次翻转都会改变上下左右和本身一共5个格子，为了将它全部翻成0，我们需要对所有情况进行遍历，判断是否可以完成，但是直接枚举每个点的情况会非常复杂，将会是2的225次方。但是，我们可以只枚举第一行的所有情况，由于第一行被确定，第二行肯定也能确定所有的情况(因为要是翻第2行的格子，会影响到上一行，而它上一行的格子已经确定)
这样我们通过枚举第一行的所有情况就能枚举所有的情况，而且我们要选的是最小步数，这里我们保证每个格子最多会被翻一次，保证最小性。
最后检验是否成立，我们只需要判断最后一行即可，当最后一行满足时，整个就满足。
3、代码模板：
#include<iostream>
#include<cstring>
using namespace std;
const int N=20;
//backup备份用,step记录哪些格子翻转了
int g[N][N],backup[N][N],step[N][N];
int n,m;
bool flag=true;//记录是否能全翻成0
int dx[5]={0,0,-1,0,1};//中 左 上 右 下
int dy[5]={0,-1,0,1,0};
void solve(int x,int y) //变化操作
{
for(int i=0;i<5;i++)
{
int tx=x+dx[i];
int ty=y+dy[i];
if(tx<0 || tx>=n || ty<0 || ty>=m)//越界跳过
continue;
g[tx][ty]^=1;
}
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%d",&g[i][j]);//读入数据
for(int op=0;op<1<<m;op++) //遍历第一行的所有情况
{
memcpy(backup,g,sizeof g);//将g备份,下次操作时恢复
memset(step,0,sizeof step);//将记录的操作重置
for(int i=0;i<m;i++) //二进制遍历第一行的所有情况
if(op>>i&1) //如果当前位上是1 代表翻转
{
solve(0,i); //翻转
step[0][i]=1; //记录下操作的位置
}
for(int i=0;i<n-1;i++) //遍历所有格子，这里还遍历第0行是因为第0行可能还有1
{
for(int j=0;j<m;j++)
{
if(g[i][j]==1) //如果有1就翻转下一行的
{
solve(i+1,j);
step[i+1][j]=1;//记录操作位置
}
}
}
flag=true;
for(int i=0;i<m;i++)
if(g[n-1][i]==1)
{
flag=false;//如果有1就不行
break;
}
if(flag)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
printf("%d ",step[i][j]);
puts("");
}
return 0;
}
memcpy(g,backup,sizeof backup);//恢复备份
}
printf("IMPOSSIBLE");
return 0;
}
投递国家电网等公司6个岗位 >