状压dp(代码片段)

关键词：

这几天都在学习状压DP，总结一下，首先是状压DP的工具。

2、一些基本操作：

     1）如何判断数字x第i位是否为1 ： 1<<(i-1) & x

     2）将一个数字x二进制下第i位更改成1 ： x = x | (1<<(i-1))

     3）把一个数字二进制下最靠右的第一个1去掉 ： x = x & (x-1）

     4）空集 ： 0

      5）只含有第i个元素的集合 i ： ( 1 << i ) -1

      6）判断第i个元素是否属于集合S ： if ( S >> i & 1 )

      7）向集合中加入第i个元素 S U i ： S | 1 << i

       8）从集合中去除第i个元素 S  i ： S & ~( 1 << i ) S - ( 1 << i )

       9）集合S和T的并集 S∪T ： S | T

      10）集合S和T的并集 S∩T ： S & T

      11）如果要将集合 0, 1, 2, … , n-1 的所有子集枚举出来的话，可以写为： for ( int S=0; S < 1<<n ; S++ ) 对子集S的处理

 分享最近做的几道状压dp的题目：

1、poj 3254  Corn Fields 

 这道题是说有m行n列格子，1可以放牛，0不行；并且相邻格子不能放牛；问你有多少中放牛方案？

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define mod 100000000
int kind[1<<13],ok[13];
int dp[13][1<<13];
int main()

    int n,m,t;
    while(~scanf("%d %d",&n,&m))
    
       int ans=0;
   //枚举锁有不相邻的情况。
       for(int i=0;i<(1<<m);i++)
         if((i&(i<<1))==0)
            kind[ans++]=i;
       memset(ok,0,sizeof(ok));
       for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
       
           scanf("%d",&t);
           if(t==0)
            ok[i]|=1<<j;
       
       memset(dp,0,sizeof(dp));
       for(int i=0;i<ans;i++)
        if((ok[0]&kind[i])==0)dp[0][kind[i]]=1;
       for(int i=0;i<n-1;i++)
        for(int j=0;j<ans;j++)
       
           if((kind[j]&ok[i])==0)
           
               for(int k=0;k<ans;k++)
               
                   if((ok[i+1]&kind[k])==0&&(kind[k]&kind[j])==0)
                    dp[i+1][kind[k]]+=dp[i][kind[j]];
                    //printf("%d\n",dp[i+1][kind[k]]);
               
           
       
       long long sum=0;
       for(int i=0;i<ans;i++)
       
           sum+=(dp[n-1][kind[i]])%mod;
       
       printf("%lld\n",sum%mod);
    

2、poj 1738 石子合并

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define MAX 105
int minn,maxn;
int n,dp1[MAX][MAX],dp2[MAX][MAX];
int sum[MAX],a[MAX];
void DP()

   //fill(dp1[0],dp1[0]+n+1,INF);
   //fill(dp2[0],dp2[0]+n+1,0);
   for(int i=1;i<=n;i++)dp1[i][0]=0;
   for(int i=1;i<=n;i++)dp2[i][0]=0;
   for(int L=1;L<n;L++)
    for(int i=1;i<=n;i++)
   
       int j=i+L;
       dp1[i][L]=INF;
       dp2[i][L]=0;
       for(int k=1;k<=L;k++)
       
           if(i+k>n)
                dp1[i][L]=min(dp1[i][L],dp1[i][k-1]+dp1[(i+k)%n][L-k]);
                dp2[i][L]=max(dp2[i][L],dp2[i][k-1]+dp2[(i+k)%n][L-k]);
           
           else 
            dp1[i][L]=min(dp1[i][L],dp1[i][k-1]+dp1[i+k][L-k]);
            dp2[i][L]=max(dp2[i][L],dp2[i][k-1]+dp2[i+k][L-k]);
           
       
        if(i+L>n)
            dp1[i][L]+=sum[(i+L)%n]+sum[n]-sum[i-1];
            dp2[i][L]+=sum[(i+L)%n]+sum[n]-sum[i-1];
           
           else 
            dp1[i][L]+=sum[i+L]-sum[i-1];
            dp2[i][L]+=sum[i+L]-sum[i-1];
           
        
   
     minn=INF;
     maxn=0;
     for(int i=1;i<=n;i++)minn=min(minn,dp1[i][n-1]);
     for(int i=1;i<=n;i++)maxn=max(maxn,dp2[i][n-1]);

int main()

   scanf("%d",&n);
   memset(sum,0,sizeof(sum));
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]+a[i];
    
    /*for(int i=1;i<=n;i++)
        printf("%d ",sum[i]);*/
    DP();
    printf("%d\n%d\n",minn,maxn);

   慢慢消化…………

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

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

dp-状压dp(代码片段)

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

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

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

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。初始化... 查看详情

状压dp(代码片段)

P2915[USACO08NOV]MixedUpCowsGdfs去做#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#definelllonglongusingnamespacestd;intb[25],n,m,a[25];llcnt;voiddfs(intt,int 查看详情

poj3254(状压dp）(代码片段)

CornFieldsTimeLimit:2000MS MemoryLimit:65536KTotalSubmissions:19518 Accepted:10243DescriptionFarmerJohnhaspurchasedalushnewrectangularpasturecomposedofMbyN(1≤M≤12;1≤N≤12)squareparcels.Hewant 查看详情

b.littleponyandharmonychest(状压dp)(代码片段)

B.LittlePonyandHarmonyChest(状压dp)考虑bi≥59b_i\\ge59bi​≥59​时，bi=1b_i=1bi​=1更优。所以只需考虑bi≤59b_i\\le59bi​≤59。又因为bbb数组两两互质。即每个质因子只能被一个数使用。且≤59\\le59≤59的质因子只有161616个。考虑... 查看详情

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

CornFieldsTimeLimit: 2000MS MemoryLimit: 65536KTotalSubmissions: 20975 Accepted: 10998DescriptionFarmerJohnhaspurchasedalushnewrectangularpasturecomposedof M by 查看详情

dp--状压dp(代码片段)

ProblemDescription互不侵犯在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。Analysisofideas把每一行的每一个状态用一个... 查看详情

flashingfluorescents(状压dp)(代码片段)

FlashingFluorescents时间限制: 1Sec  内存限制: 128MB提交: 56  解决: 19[提交][状态][讨论版][命题人:admin]题目描述Youhavenlights,eachwithitsownbutton,inaline.Pressingalight’sbuttonwilltoggl 查看详情

cf580dkefaanddishes状压dp(代码片段)

WhenKefacametotherestaurantandsatatatable,thewaiterimmediatelybroughthimthemenu.Therewerendishes.Kefaknowsthatheneedsexactlymdishes.Butatthat,hedoesn‘twanttoorderthesamedishtwicetotasteasmanydishesasp 查看详情

集合划分（状压dp）(代码片段)

...满足1≤ai≤991\\leqa_i\\leq991≤ai​≤99分析代码/*集合划分状压dp*/#include<bits/stdc++.h>usingnamespacestd;con 查看详情

hiewiththepie（poj3311）状压dp(代码片段)

DescriptionThePizazzPizzeriapridesitselfindeliveringpizzastoitscustomersasfastaspossible.Unfortunately,duetocutbacks,theycanaffordtohireonlyonedrivertodothedeliveries.Hewillwaitfor1ormore(upto10)order 查看详情

poj292301背包+状态压缩/状压dp(代码片段)

题目链接EmmaandEricaremovingtotheirnewhousetheyboughtafterreturningfromtheirhoneymoon.Fortunately,theyhaveafewfriendshelpingthemrelocate.Tomovethefurniture,theyonlyhavetwocompactcars,whichcomplicatesevery 查看详情

hiewiththepie-状压dp(代码片段)

 http://poj.org/problem?id=3311 #include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;constintINF=0x3f3f3f3f;inte[15][15];intdp[1<<15][15];intmain() 查看详情

状压dp入门(代码片段)

引题状压dp，全称为状态压缩动态规划，是一种利用二进制的数来表示状态的动态规划我们经常用二进制中某一位的1表示选取这一位表示的状态，用0表示相反的意义例如：现在有一张有(n)个节点的图，我们需要找到经过某些特... 查看详情

[scoi2005]互不侵犯(状压$dp$)(代码片段)

题目链接Solution状压(dp).(f[i][j][k])代表前(i)列中,已经安置(j)位国王,且最后一位状态为(k).然后就可以很轻松的转移了...记忆化搜索还是不够啊...只能会正向(dp).Code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;llf[10][101][1100], 查看详情

poj3254cornfields状压dp(代码片段)

CornFieldsTimeLimit: 2000MS MemoryLimit: 65536KTotalSubmissions: 21931 Accepted: 11470DescriptionFarmerJohnhaspurchasedalushnewrectangularpasturecomposedof M by 查看详情