正文 

当前位置： 首页 > java > java教程

算法复习——状压dp

author author     2022-09-20     665

关键词：

状压dp的核心在于，当我们不能通过表现单一的对象的状态来达到dp的最优子结构和无后效性原则时，我们可能保存多个元素的有关信息··这时候利用2进制的01来表示每个元素相关状态并将其压缩成2进制数就可以达到目的····此时熟悉相关的位运算就很重要了····以下是常见的一些需要位运算方法

技术分享

技术分享

然后说实话状压dp其它方面就和普通dp差不多了···它不像数位区间树形那样或多或少好歹有自己一定套路或规律····如何想到转移方程和状态也就成了其最难的地方···

例题：

1.Corn Fields（poj3254）

Description

Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can‘t be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.

Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.

Input

Line 1: Two space-separated integers: M and N 
Lines 2..M+1: Line i+1 describes row i of the pasture with N space-separated integers indicating whether a square is fertile (1 for fertile, 0 for infertile)

Output

Line 1: One integer: the number of ways that FJ can choose the squares modulo 100,000,000.

Sample Input

2 3
1 1 1
0 1 0

Sample Output

9

Hint

Number the squares as follows:
1 2 3
  4  

There are four ways to plant only on one squares (1, 2, 3, or 4), three ways to plant on two squares (13, 14, or 34), 1 way to plant on three squares (134), and one way to plant on no squares. 4+3+1+1=9.
 
很明显用二进制储存每一排的种植情况f[i][j],i为行，j为种植状态··每次枚举判断该行是否与玉米田本身冲突（不该种植的地方是否种上玉米），该行是否与自己冲突，该行是否与上一行冲突（相邻地方是否种上玉米）然后更新就可以了。
另外这道题的时间复杂度注意是不会超的······放心枚举····但要先枚举上一行的合法状态
然后不清楚位运算顺序的（就是我）多打几个括号吧2333
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int N=15;
const int mod=1e+8;
int f[N][5000],map[N],n,m,ans,maxx;
inline int R()
{
  char c;int f=0;
  for(c=getchar();c<‘0‘||c>‘9‘;c=getchar());
  for(;c<=‘9‘&&c>=‘0‘;c=getchar())
    f=(f<<3)+(f<<1)+c-‘0‘;
  return f;
}
inline void solve()
{
  for(int i=0;i<maxx;i++)
    if(((i|map[1])==map[1])&&!(i&(i>>1)))
      f[1][i]=1;
  for(int i=2;i<=n;i++)
    for(int j=0;j<maxx;j++)
      if(f[i-1][j])
        for(int k=0;k<maxx;k++)  
          if(((k|map[i])==map[i])&&!(k&(k>>1))&&!(k&j))
            f[i][k]=(f[i][k]+f[i-1][j])%mod;
  for(int i=0;i<maxx;i++)
    ans=(ans+f[n][i])%mod;
}
int main()
{
  //freopen("a.in","r",stdin);
  n=R(),m=R();int a;maxx=(1<<m);  
  for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
      a=R();
      if(a)  map[i]|=(1<<(j-1));    
    }
  solve();
  cout<<ans<<endl;
  return 0;
}

 

 




[noip复习知识点][个人向]zackzh

只是列列一些要复习的，努力复习吧，有种noip退役的赶脚。 一、模拟  (这你也不会？退役吧)二、DP  1.基础dp  2.区间dp  3.状压dp  4.树形dp  6.概率（期望）dp   7.环形dp&nbs... 查看详情

一些需要复习的

图SPFA（只会dijkstra）最小生成树 ① ②问题背包状压dpDFSBFS 优化dp高精度归排树形dp并查集数据结构树状数组（线段树常数卡炸）优先队列SET如果都会，那就好了呢 查看详情

算法复习——区间dp

感觉对区间dp也不好说些什么直接照搬讲义了2333例题：1.引水入城（洛谷1514）这道题先开始看不出来到底和区间dp有什么卵关系····首先肯定是bfs暴力判一判可以覆盖到哪些城市····无解直接输出···有解得话就要想想了···... 查看详情

算法系列学习状压dp[kuangbin带你飞]专题十二基础dp1d-doinghomework

https://vjudge.net/contest/68966#problem/Dhttp://blog.csdn.net/u010489389/article/details/192187951#include<iostream>2#include<cstdio>3#include<cstring>4#include<string>5#inclu 查看详情

算法复习——背包dp

1.01背包  二维递推式子：   代码：  for(i=1;i<=n;i++)for(x=m;x>=1;x--)if(x>=w[i])f[i][x]=max(f[i-1][x-w[i]]+c[i],f[i-1][x]);elsef[i][x]=f[i-1][x];printf("%d",f[n][m]);// 查看详情

sos_dp算法(代码片段)

Codeforces博客简介：前置知识：状压dpSumoverSubsetsdynamicprogramming，简称Sosdp,状压dp的一种用一个列题引出SOSdp：给你一个由2N2^N2N个整数组成的确定数组A，我们需要计算对于任意的x，F(x)=所有A[i]的和sumF(x)=... 查看详情

51nod1920空间统计学状压dp(代码片段)

...x统计曼哈顿距离为x的有序点对数。\(n\leq2*10^5,m\leq9\)。【算法】状压DPm范围很小，考虑设计状压DP的状态，可以想到设到达某个坐标j（将m维坐标压成m位四进制数）步数为k（距离等价于步数）的点数，但是难以转移。考虑按维转... 查看详情

状压dp小结

1.要状压的那一维，所有有关的下标要从0开始，而不是从1开始2.预处理很重要，可以说基本所有的状压dp都要有预处理这玩意 查看详情

hoj2662经典状压dp//myfirst状压dp

题目链接：http://acm.hit.edu.cn/hoj/problem/view?id=26621.引言：用dp解决一个问题的时候很重要的一环就是状态的表示，一般来说，一个数组即可保存状态。但是有这样的一类题目，它们具有dp问题的特性，但状态中所包含的信息过多，... 查看详情

动态规划---状压dp2(代码片段)

今天模拟，状压dp又没写出来。。。还是不会啊，所以今天搞一下这个状压dp。这里有一道状压dp的板子题：CornFields就是一道很简单的状压裸题，但是要每次用一个二进制数表示一行的状态。附加一个关于位运算的总结：上题干... 查看详情

状压dp(代码片段)

这几天都在学习状压DP，总结一下，首先是状压DP的工具。类型符号规则例子按位与&同1为1，其余为09       00001001&5       000001011      &nb 查看详情

foreignnumber[状压dp]

...leInput　　123455SampleOutput　　24HINT　　Solution　　我们运用状压DP，令f[j][opt]表示当前余数为j，状态为opt的方案。　　状态记录的是：各个数字被用了几次。　　那么我们就可以状压了。先 查看详情

第一次接触状压dp(代码片段)

状压DP入门及理解*（另类的暴力）*    一般状态数不多的时候就会开数组，但是有的状态并不好表示，于是，状压DP就产生了。   状压DP应该是分两类的，一类是压缩状态，另一类是舍弃状态。  &... 查看详情

fzu2188状压dp

G-SimpleStringProblemTimeLimit:2000MS    MemoryLimit:32768KB    64bitIOFormat:%I64d&%I64uSubmitStatusPracticeFZU2218DescriptionRecently,youhavefoundyourinte 查看详情

dp-状压dp(代码片段)

...w.bilibili.com/video/BV1Z4411x7Kw?from=search&seid=13855865082722302053状压介绍：状态表示：  转移方程：i是当前节点，j是下一步要走的节点  子集枚举：核心代码：1。由当前枚举未知首先枚举状态，枚举S中包含的节点：枚... 查看详情

d.romanandnumbers(状压dp)(代码片段)

D.RomanandNumbers(状压dp)把nnn的每一位状压，问题等价于选择一个顺序走完这cntcntcnt个位使得(modm)=0\\pmodm=0(modm)=0答案。令dp[i][j]dp[i][j]dp[i][j]表示状态iii模mmm余jjj的答案。转移时需要注意最高位对应的数不能为000。初始化... 查看详情

poj2411mondriaan'sdream（状压dp）

【POJ2411】Mondriaan‘sDream（状压dp）TimeLimit:3000MS MemoryLimit:65536KTotalSubmissions:14107 Accepted:8152DescriptionSquaresandrectanglesfascinatedthefamousDutchpainterPietMondriaan.Onenight,aft 查看详情

simplestringproblem（状压dp）(代码片段)

SimpleStringProblemRecently,youhavefoundyourinterestinstringtheory.Hereisaninterestingquestionaboutstrings.YouaregivenastringSoflengthnconsistingofthefirstklowercaseletters.Youarerequiredtofindtwonon- 查看详情