POJ 1038 Bugs Integrated Inc （复杂的状压DP）-白红宇

POJ 1038 Bugs Integrated Inc （复杂的状压DP）

阅读量：4631 次

发布时间：2019-06-09

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

（复杂的状压DP）

$solution:$

很纠结的一道题目，写了大半天，就想练练手，结果这手生的。其实根据之前那道炮兵阵地就不应该写的，但是总觉得自己的思路会好一些，码量又小。

博主的核心思路其实就是用一个二进制数来压缩三行的状态，因为二进制的左移右移很方便。然后就是如果三进制会很不好转移。

我们可以用一个二进制数来预处理压缩出第 $i$ 往下三行的障碍状态，前 $m$ 个二进制位表第 $i$ 行，中间 $m$ 个二进制位表 $i+1$ 行，后 $m$ 个二进制位表第 $i+2$ 行

我们设一个长方体用坐上角那个点表示

我们可以用搜索来搜出一行内的长方体放置方案，这个很好写，线面代码里唯一一个手写函数就是用来求这个的。它同样用一个二进制来表示出，这个方案里三行被长方体覆盖的状况。

然后我们需要用步骤3里的单行放置方案来求出上下两行的方案拼接方案（其实就是用一个二进制将两行的方案压缩进来）。直接暴力枚举单行放置方案，再用二进制与运算来判断是否有冲突：如下

for(rg i=1;i<=tt;++i)             for(rg j=1;j<=tt;++j)                         if(!((b[i]>>m)&b[j])){                             r[++st]=j; p[i][j]=st; //r表示方案的下面一行用的那个单行方案                             g[st]=(b[i]>>m)|b[j]; //找出两行的放置方案                         }

然后我们设状态就必须将前两行的状态都包含进去：设 $f[i][j]$ 表示第 $i$ 行前两行状态为 $g[j]$ 意义在上面代码里

然后我们就可以开始常规转移，但是数组 $r$ 和数组 $p$ 一定要搞清楚！

$code:$

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #define ll long long#define db double#define rg register intusing namespace std;int n,m,ff,tt,st,ans;int a[155];int b[305];int c[305];int g[3005];int r[3005];int p[305][305];int f[155][3005];inline void dfs(int i,int v,int vv){ //用一个二进制表示一行的状态（在某一行放，下面两行都有可能被覆盖，用一个二进制将这三行压在一起） if(i==m){b[++tt]=v; c[tt]=vv; return ;} dfs(i+1,v,vv); //导入方案 if(i+3<=m)dfs(i+3,v|(7<
                
                 <<(i+m)),vv+1); //放入横的长方体 if(i+2<=m)dfs(i+2,v|(3<
                 
                  <<(i+m)|(3<<(i+m+m))),vv+1); //放入竖的长方体}int main(){ rg t; cin>>t; while(t--){ cin>>n>>m>>ff; ans=0; //读入 memset(a,0,sizeof(a)); memset(f,0,sizeof(f)); tt=0; st=0; dfs(0,0,0); //初始化 for(rg i=1;i<=tt;++i) for(rg j=1;j<=tt;++j) if(!((b[i]>>m)&b[j])){ r[++st]=j; p[i][j]=st; //r表示方案的下面一行用的那个单行方案 g[st]=(b[i]>>m)|b[j]; //找出两行的放置方案 } for(rg i=1;i<=ff;++i){ rg x,y; cin>>x>>y; a[x]|=1<<(y-1); } a[n+1]=(1<
                  
                   >m)|a[i])&b[k])){ //这一行放的方案与前面的方案还有障碍不会冲突 f[i][p[r[j]][k]]=max(f[i][p[r[j]][k]],f[i-1][j]+c[k]); ans=max(ans,f[i][p[r[j]][k]]); //因为多加了一行障碍，不用怕出界 } } printf("%d\n",ans); } return 0;}

转载于:https://www.cnblogs.com/812-xiao-wen/p/11210405.html

你可能感兴趣的文章

（复杂的状压DP）

\(solution:\)

\(code:\)