对状压dp的一点理解

时间:2023-03-10 00:39:48
对状压dp的一点理解

 此dp可以理解为最暴力的dp,因为他需要遍历每个状态,所以将会出现2^n的情况数量,所以明显的标志就是数据不能太多(好像是<=15?),然后遍历所有状态的姿势就是用二进制来表示,01串,1表示使用,0表示未使用,就把所有的状态投射到很多二进制的数上(类似于hash?)然后对每个状态找上一"些"状态的方法如下代码,即状压dp的精髓!!!

  

 

for(s=1;s<(1<<15);s++)
{
  for(i = n-1 ; i >=0;i--)
  {
    tem=1<<i; // 1在某一位,其它位为0
    if(tem & s) //判断是否能由此种状态达到,即判断当前位是1还是0
    {  
      past=s-tem; //当前位的1变为0即为上一状态
    }
  }
}