POJ 3254 Corn Fields 状态压缩-白红宇

POJ 3254 Corn Fields 状态压缩

阅读量：6471 次

发布时间：2019-06-23

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

这题对我真的非常难。实在做不出来，就去百度了，搜到了一种状压DP的方法。这是第一种

详细见凝视

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 using namespace std;#define mod 100000000int n,m,map[15];//map数组用来存图int cnt[10000],dp[15][10000];//cnt存当一层每处都能够放置东西时，全部满足题意的情况int k;bool ok(int x)//推断某种方法是否满足题意{ if(x&(x<<1)) return false; //假设某点左右有点的话，返回false return true;}void find(){ for(int i=0;i<(1<
                 
                  >n>>m) { memset(map,0,sizeof(map)); for(i=0;i
                  
                   >temp; if(!temp) map[i]|=1<

另外一种方法是状态压缩+记忆化搜索。这是我从瓜神那看来的记忆化搜索，然后依据我从上个代码中学来的东西改进了下，QAQ。要学的东西还有非常多。慢慢来吧

主要思路是从第一层開始向下搜索，假设搜到符合条件的就继续向下搜索，直到最后一行为止

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define maxn 20#define mod 100000000int map[maxn];int dp[maxn][1<<12];int n,m;bool ok(int i,int state,int cur){    if(map[cur]&i) return false;//推断是否会把东西放在不能放东西的地方    if(i&(i<<1)) return false;//推断东西的左右是否放置了东西    if(cur)    {        if(state&i) return false;//推断东西的上边是否放置了东西    }    return true;}int dfs(int cur,int state){    if(cur==n) return dp[cur][state]=1;    if(dp[cur][state]!=-1) return dp[cur][state];//记忆化搜索    int ret=0;    for(int i=0;i<(1<
          
           >n>>m; memset(map,0,sizeof(map)); memset(dp,-1,sizeof(dp)); for(int i=0;i
           
            >t; if(!t) map[i]|=1<