状态压缩dp二进制状态压缩是不是只能表示32个数据

来源：蜘蛛抓取(WebSpider) 时间：2017-07-24 08:39 标签： 状态压缩dp讲解
POJ 2923 Relocation 状态压缩DP + 0-1背包
比较综合的题目。
题意：有n个物品，有两辆车载重分别是c1,c2.问需要多少趟（c1，c2一起运一次就算1趟）能把物品运完。n比较小，只有10，而且需要把所有物品全部运完，便想到状态压缩来保存状态。首先记录好所有的可行状态，对于状态state能一趟运完。然后再利用01背包，dp[j]，表示已运的状态为j，如果状态j与state[i]不冲突，则可以从状态j运一趟变为j|state[i]。
#include&stdio.h&
#include&string.h&
#include&algorithm&
int n,w[11];
int dp[1026];
int state[1026];
bool vis[1026];
int num,sum, c1, c2;
bool judge(int zt)//判断zt这个状态能不能由c1，c2共同运送一次就能完成。
memset(vis,0,sizeof(vis));
vis[0]=1;sum=0;
for(i=0;i&n;i++)
if(zt&(1&&i))//第i个物品属于这个状态
sum+=w[i];
for(j=c1;j&=w[i];j--)//0-1背包
if(vis[j-w[i]])vis[j]=1;
for(i=0;i&=c1;i++)
if(vis[i]&&sum-i&=c2)return 1;//判断c1，c2运送一次就能把这个状态完成。
int main()
int cas, i, j, X=1;
scanf("%d",&cas);
while(cas--)
scanf("%d%d%d",&n,&c1,&c2);
for(i=0;i&n;i++)//注意必须从0开始读入，不然会影响二进制运算。
scanf("%d",&w[i]);
for(i=0;i&(1&&n);i++)
if(judge(i))state[num++]=i;
memset(dp,127,sizeof(dp));//赋值正无穷，int范围最大值
for(i=0;i&i++)//dp[i]表示运走二进制组合数为i的货物最少需要几趟，i表示一个状态
for(j=((1&&n)-1)-state[i];j&=0;j--)
if(!(j&state[i]))//if这句话可以不写，但它的存在更能体现对dp的理解
dp[j|state[i]]=min(dp[j|state[i]],dp[j]+1);
printf("Scenario #%d:\n%d\n\n",X++,dp[(1&&n)-1]);
Copyright (C)2017
All rights reserved.暑假集训（59）
做了这一题，大概明白状态压缩是怎么回事了。。。&参考了牛人的代码~代码涉及的位运算不多，还好理解，有些大牛用来了很多位运算技巧，直接看不懂
poj 3254 Corn Fields &
输入m行n列的数字，其中为1或者是0，1表示土壤肥沃可以种植草地，0则不可以。在种草地的区域可以放牛，但相邻的四个区域不允许同时放牛，问有多少种放牛的方法？
由m,n&=12,可用状态压缩
对于第i行，可以放草的格子置为0，不可以种草的格子设置为1，整一行的状态存入map[i]中（与题目中给出的相反，后面解释）
对于每一行，放牛的格为1，不放牛的格为0，整行用一个二进制数表示
dp[i][j]表示第i行放牛状态为j时有多少种方法，易知：
&1.首先j必须合法，即左右相邻两位不同时出现1，运行时可以先选取合法的状态加入数组
void init()
for(int i=0; i&(1&&m); i++) //舍去存在连续是1的状态
int temp=i&&1;
if(i&temp)
state[++cnt]=i;//各种放牛的状态
}&2.不能在不能种草的地方放牛，即 &map[i]+state[j]!=(state[j]|map[i]) &
&3.dp[i][j] = SUM(dp[i-1][k]),其中state[k]+state[j]!=(state[k]|state[j]),即上下相邻位置不放牛
由此，可以求出所有的dp[i][j]，那么放牛的种类共有 = SUM(dp[n-1][j])最后一行所有状态的放牛种类之和
//AC CODE：
#include&iostream&
#include&cmath&
#include&algorithm&
#include&vector&
#include&cstdio&
#include&cstdlib&
#include&cstring&
#include&string&
#define MOD
int dp[13][3000];
int n,m,map[12],
int state[3000];
void init()
for(int i=0; i&(1&&m); i++) //舍去存在连续是1的状态
int temp=i&&1;
if(i&temp)
state[++cnt]=i;//各种放牛的状态
int main()
int i,j,x,k;
scanf(&%d%d&,&n,&m);
memset(map,0,sizeof(map));
memset(dp,0,sizeof(dp));
for(i=0; i&n; i++)
for(j=0; j&m; j++)
scanf(&%d&,&x);
map[i]=map[i]&&1;//map[i]中的二进制压缩，1表示土壤贫瘠，0表示肥沃，正好和题中说的相反
map[i]+=(x^1);
//初始化第一行
for(i=1; i&= i++)
//放牛的格为1，不放牛的格为0，1表示土壤贫瘠，0表示肥沃
if(map[0]+state[i]==(state[i]|map[0]))
dp[0][i]=1;
//初始化其它行
for(i=1; i&n; i++)
for(j=1; j&= j++)
if(map[i]+state[j]!=(state[j]|map[i]))//该状态不存在
for(k=1; k&= k++)//该状态存在 +上一行的值
if(state[k]+state[j]!=(state[k]|state[j]))
//上一行草与该行类似，有草的地方有，米草的地方也有
比如：草：0101 牛：1010
上一行：0000
dp[i][j]+=dp[i-1][k];
if(dp[i][j]&=MOD)
dp[i][j]-=MOD;
//计算结果
int sum=0;
for(i=1; i&= i++)
sum+=dp[n-1][i];
if(sum&=MOD)
printf(&%d\n&,sum);
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：266565次
积分：3888
积分：3888
排名：第7855名
原创：130篇
转载：56篇
评论：42条
(39)(2)(1)(1)(3)(3)(5)(8)(7)(8)(23)(44)(3)(8)(10)(23) 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
状态压缩DP入门
下载积分：1000
内容提示：状态压缩DP入门
文档格式：PPT|
浏览次数：64|
上传日期： 00:52:26|
文档星级：
全文阅读已结束，如果下载本文需要使用
 1000 积分
下载此文档
该用户还上传了这些文档
状态压缩DP入门
官方公共微信

我要回帖

更多关于 状态压缩dp讲解 的文章

 

随机推荐