状压$DP$练习-白红宇

状压$DP$练习

阅读量：4628 次

发布时间：2019-06-09

本文共 2512 字，大约阅读时间需要 8 分钟。

;

思路出来有点有意思：是树型加状压的转移。

将分部压掉就可以了

但我是挂在了初始化上……

$QAQ$

#include
    
     using namespace std;inline int read(){    int f=1,w=0;char x=0;    while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();}    while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();}    return w*f;}const int N=101;int n,m,t;int val[4100],cost[101][20];int head[4*N],num_edge,dp[401][4100];struct Edge{int next,to;} edge[4*N];inline void add(int from,int to){    edge[++num_edge].next=head[from];    edge[num_edge].to=to;    head[from]=num_edge;}inline void dfs(int pos,int fa){    for(int i=head[pos];i;i=edge[i].next)        if(edge[i].to!=fa)        {            dfs(edge[i].to,pos);            for(int j=(1<

现在才发现，状压$DP$的状态很考思维，即你的状态和你的转移有很大关系。

如果，你的状态压的好，就会很简化方程，相反如果你的状态一般，很有可能不太好转移甚至是无法转移！

这一题的状态很有意思，其实一开始我想的是横着放的标为$0$,竖着放的标为$1$。

但是有一个极为明显的问题：

像这样的状态，就会有无法判定当前行和上一行的关系，状态不能对应（相当于是无法判定竖着放的是否残缺）

因此就有这样的状态，很有意思：横着放的为$1$,而竖着放的上$0$下$1$,这样就很巧妙的避免了上面的问题。

相当于我们用$1$来判定了当前位置是否为一个结束。

那么转移就很好办了，状压的转移一般只要手玩一下就可以了吧（也许是我还没做到这样的毒瘤题？$QwQ$）

嘿呀，上代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #include 
                
                 //忍不住要吐槽poj的头文件，真的恶心哈using namespace std;inline int read(){ int f=1,w=0;char x=0; while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();} while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();} return w*f;}int n,m;long long f[15][1<<12];inline bool FirLin(int s){ for(int i=0;i

下一个：一个三进制的状压$DP$，说实话，我以前的思维被二进制的状压禁锢，应该说没有考虑过其他进制。

观察可得，显然当前行的状态与前两行的状态有关系，不妨将前两行压在一起，用一个三进制表示，具体的压法为：

$0$表示$i$和$i-1$行都没有放;$1$表示$i$行没放$i-1$行放了;$2$表示$i$和$i-1$行都放了

转移时分个类，讨个论即可：

上代码了呦！

//0表示i和i-1行都没有放//1表示i行没放i-1行放了//2表示i和i-1行都放了#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #include 
                
                 //忍不住要吐槽poj的头文件，真的恶心哈using namespace std;inline int read(){ int f=1,w=0;char x=0; while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();} while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();} return w*f;}int n,m,k,las,now,c;int a[200][30],pw[20],f[2][60000];inline int Las(int i) {return las/pw[i-1]%3;}inline int Now(int i) {return now/pw[i-1]%3;}inline void Dfs(int Lin,int cnt)//在基础状态上跑出所有可能的放法{ if(Lin>m) return ; if(Lin