从品牌网站建设到网络营销策划,从策略到执行的一站式服务
今天我们先来讲一下状态压缩dp(也称状压dp)。状压dp,顾名思义,就是把状态压缩起来。比如对于8*8 的棋盘,每个位置可以放一个棋子,对于在第i行第2个位置和第6个位置放了棋子,我们可能需要8维或9维数组表示。因此我们就有了把一行状态压缩成一个数字的做法。一般我们会转化为二进制,如果每个位置可以有3种状态,那我们可以采用三进制。这样只需要一个大小为2^8的一维数组我们就可以存下所有状态,这就是状态压缩。
成都创新互联是一家专业提供宽甸企业网站建设,专注与成都网站制作、成都网站建设、外贸营销网站建设、H5开发、小程序制作等业务。10年已为宽甸众多企业、政府机构等服务。创新互联专业网站建设公司优惠进行中。
eg1 • 现在有 n*m 的方格棋盘,和无限的 1*2 的骨牌,问有多少种方法能用骨牌 铺满棋盘。 • 1<=n,m<=11. 算法分析: 首先 n*m 是奇数一定拼不出来。使用状态压缩,如果第 i 个位置上放骨牌,就在二进制对应位置填 1,否则是 0. 用 f[i][s] 表示填到了第 i 行状态是 s 的方案数。答案就是 f[n][(1<m) { return ; } if(i==m) { ++tot; from[tot]=pre; to[tot]=now; return ; } dfs(i+2,now<<2|3,pre<<2|3); dfs(i+1,now<<1,(pre<<1)|1); dfs(i+1,now<<1|1,pre<<1); } 主函数: int f[12][1<<11]; dfs(0,0,0); f[0][(1<
本文标题:编程兔暑假3.5阶段集训Day6——状压(状态压缩)dp、dp优化以及图论
URL分享:http://cdkjz.cn/article/dsoigjd.html
成都网站建设公司地址:成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220
成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.
专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网! | 成都网站建设哪家好? | 网站建设地图