【动态规划】状压dp

概念利用计算机二进制的性质来描述状态的一种DP方式。n位0/1状态 需要2 n 1 − 1 2^{n 1} - 12n1−1十进制数状压其实是一种很暴力的算法因为他需要遍历每个状态所以将会出现2^n的情况数量不过这并不代表这种方法不适用一些题目可以依照题意排除不合法的方案使一行的总方案数大大减少从而减少枚举来自https://www.cnblogs.com/ljy-endl/p/11627018.html做法适合物品数很少每个物品有两个状态的问题开关灯/选不选用二进制每一位0/1代表两个状态用一个数表示物品组合起来的状态从上一个状态转移过来可以使用BFS或DP数组位运算对集合进行操作判断a的第i位是否1 1(i-1)a把a的第i位改成1 a|(1(i-1))把a的第i位改成0 a(~(1(i-1)))把a的最后一个1去掉 a(a-1)P3602#includebits/stdc.h#defineendl\n#defineforr(i,l,r)for(intil;ir;i)#definereforr(i,l,r)for(intir;il;i--)#defineintlonglongusingnamespacestd;constintINF0x3f3f3f3f;/* void solve() { int w,n;cinnw; vectorintc(n1),buc; //迭代加深 auto dfs[](auto self,int x,int num)-bool{//x奶牛号 num容器数 for(int i1;inumix;i){//bfs找能不能放进每一个容器 //ix 第i奶牛放到i后车厢没有意义 ix是一个奶牛一个车厢 每个车厢都是一样的这样防止重复计算 if(c[x]buc[i]w){//能放进去 buc[i]c[x]; if(xn)return 1; if(self(self,x1,num))return 1; buc[i]-c[x]; } } return 0; }; forr(i,1,n){ cinc[i]; } forr(i,1,n){ bucvectorint(n1,0); if(dfs(dfs,1,i)){ coutiendl; return; } } } */voidsolve(){//状压dpintw,n;cinnw;vectorintc(n1);forr(i,1,n){cinc[i];}intuppow(2,n);vectorvectorintdp(n1,vectorint(up1,INF));//dp记录每个电梯 每个状态的重量forr(i,1,n){//放一头牛的状态dp[1][1(i-1)]c[i];}forr(i,1,n){//电梯数量forr(j,1,up-1){//对每一个状态if(dp[i][j]!INF){//状态存在 就向外转移forr(k,1,n){//转移到其他牛if(j(1(k-1)))continue;//已经包含了这头牛跳过if(dp[i][j]c[k]w)dp[i][j(1(k-1))]min(dp[i][j]c[k],dp[i][j(1(k-1))]);//能放进去else{dp[i1][j(1(k-1))]c[k];//超重了 放到新的电梯里}}}}}forr(i,1,n){if(dp[i][up-1]!INF){coutiendl;//找最小的能装下11111... 的情况break;}}}P2040 大佬的神奇状压注意到每次所处状态是从上一次状态点灯转移而来使用状压#defineforr(i,l,r)for(intil;ir;i)#definereforr(i,l,r)for(intir;il;i--)#defineintlonglongusingnamespacestd;constintN12;bitset9mp[9]{0b110100000,0b111010000,0b011001000,0b100110100,0b010111010,0b001011001,0b000100110,0b000010111,0b000001011};//每个灯点亮的状态变化voidsolve(){intnow0;forr(i,0,8){intc;cinc;nowc*(1i);}vectorintans(520,-1);//记录答案queueintp;//队列存状态ans[now]0;p.push(now);while(!p.empty()){nowp.front();//当前的状态p.pop();forr(j,0,8){if(ans[now^mp[j].to_ulong()]-1){//没走过ans[now^mp[j].to_ulong()]ans[now]1;//状态转移p.push(now^mp[j].to_ulong());}}}coutans[511]endl;}P2622 依旧关灯问题可以看到n、m范围很小可以使用二进制表示开关灯状态以选或不选某个按钮进行BFS找到第一个全关灯的状态就退出找最短路径。constintN105,M1050;constdoublePIacos(-1);constlonglongmod1e53,inf1e1810;inta[N][N],vis[M];voidsolve(){intn,m;cinnm;forr(i,1,m){forr(j,1,n)cina[i][j];}//二进制状态压缩 BFS 先退出找最小代价queuepiiq;q.push({(1n)-1,0});vis[(1n)-1]1;while(q.size()){auto[now,stp]q.front();q.pop();if(now0){returncoutstpendl,void();}forr(i,1,m){intxnow;forr(j,1,n){if(a[i][j]-1)x|(1(j-1));if(a[i][j]1)x((1n)-1-(1(j-1)));}if(vis[x]0){vis[x]1;q.push({x,stp1});}}}cout-1endl;}POJ2411 Mondriaan’s Dream对每一个位置只用从上往下更新分析intdp[2][1111];voidsolve(intn,intm){if(nm)swap(n,m);memset(dp,0,sizeofdp);intnow0,old1;//现在的now是第0行dp[now][(1m)-1]1;//第一行上面全铺满forr(i,1,n){forr(j,1,m){swap(now,old);memset(dp[now],0,sizeofdp[now]);forr(k,0,(1m)-1){//k51 转移到 x0if(k(1(m-1)))dp[now][(k1)(~(1m))]dp[old][k];//k50 - x1竖 (而且得有上一行k5的空)if(i1!(k(1(m-1))))dp[now][(k1)^1]dp[old][k];//k51 k00 - x1横 k01 (得有上一列k0)if(j1(!(k1))(k(1(m-1))))dp[now][((k1)|3)(~(1m))]dp[old][k];}}}coutdp[now][(1m)-1]endl;}十二届蓝桥杯省A 回路计数二进制状态记录已经经过的点集定义状态我们需要知道两件事才能继续往下走当前已经走过了哪些点用状态掩码s ss表示当前停留在哪个点用点编号i ii表示因此定义d p [ s ] [ i ] dp[s][i]dp[s][i]为从起点出发经过点集s sss ss是一个二进制整数最后恰好停在点i ii的路径数量。初始化起点是第 1 栋教学楼注意代码中通常用 0-index即第 0 号点。初始状态只包含起点s 1 0 1 s 1 0 1s101。初始方案数d p [ 1 ] [ 0 ] 1 dp[1][0] 1dp[1][0]1。状态转移方程我们要计算d p [ s ] [ i ] dp[s][i]dp[s][i]即“走了一通集合s ss最后停在i ii”的方案数。这意味着最后一步是从某个点j jj走到i ii的。点j jj必须在集合s ss中除去i ii之外的部分。点j jj和点i ii之间必须有边即互质。转移方程为d p [ s ] [ i ] ∑ d p [ s ∖ { i } ] [ j ] dp[s][i] \sum dp[s \setminus \{i\}][j]dp[s][i]∑dp[s∖{i}][j]其中求和条件是j ∈ s j \in sj∈s且j ≠ i j \neq iji且gcd ⁡ ( i , j ) 1 \gcd(i, j) 1gcd(i,j)1。constintN25,M1e5;constdoublePIacos(-1);constlonglongmod998244353,inf1e18;constintST121;intg[N][N],dp[ST5][N];//dp[已经路过的点集][当前所在的点]到这个点的方案数voidsolve(){intn21;forr(i,1,n){forr(j,i1,n){if(__gcd(i,j)1)g[i-1][j-1]g[j-1][i-1]1;}}dp[1][0]1;// 从1开始forr(s,0,ST-1){// 遍历每个状态forr(i,0,n-1){// 状态中每个点 作为新到达的点if((si)1){forr(j,0,n-1){// 上一个状态s-(1i) 之前遍历过j点 并且ij之间联通if(((s-(1i))j1)g[i][j])dp[s][i]dp[s-(1i)][j];//dp[包含i的状态][i] dp[不包含i的状态][j];}}}}intans0;forr(i,1,n-1)ansdp[ST-1][i];coutansendl;// cout881012367360endl;}