注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Hdu1693】【插头DP】【Eat the Trees】  

2014-04-29 15:59:56|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    0.0 WY貌似会吞题解?上次把梦幻布丁吞了,这次把A+B吞了233。 
    题目大意:给出一个N*M的带障碍的地图,求这个地图的路径的个数,使得每一个格子都与相邻两个格子相连。【可以不连通】
    推荐的ppt自然就是cdq的《基于连通性状态压缩的动态规划问题》
    学习了一下插头DP。首先要了解的就是 轮廓线和插头。0.0咱们的插头DP是,从上往下,从左到右进行dp,然后考虑当前dp的格子 i,j,此时已经dp了的格子与未dp的格子存在一条分界线,这条分界线咱们称它为轮廓线,而轮廓线两边的格子的连通性咱们就称为插头。
     dp有两个要素,一个就是状态表示,一个就是转移。这里首先提到的就是状态表示,咱们考虑直接搜索的话,实际上也是自上往下,自左到右地dp,即同样会产生轮廓线,同样的也会产生插头,咱们注意到这一点之后就会发现,咱们实际上就可以利用插头作为dp的状态,咱们的状态可以由以下两个因素确定:
     1)轮廓线
     2)插头
     第一个可以由当前dp的格子得到轮廓线,第二个可以用一个n+1位的三进制数来表示这个插头的形式【为什么是三进制请看cdq的ppt 】【不过这道题目实际上二进制就可以了
      即用 f[i][j][S]表示一个状态,S是一个三进制数。
      接下来考虑转移,转移分为两种,一种是换行的转移:这个需要讨论一下。
      首先由于某一行最后的那个状态必然最后一位得是0,所以咱们把这个状态右移一位,然后再讨论第一位的情况,如果第一位是0的话【cdq的#】,那么咱们显然得让下一行的第一个的前两个插头为12,然后如果第一位是1的话,显然咱们需要讨论让前两个插头的一个为1,一个为0。然后这样转移即可。【这里是递推法】
      一种就是普通的转移,从 格子i,j转移到 格子 i,j+1,这里的转移也需要讨论一下:
      首先考虑i,j的状态S的第j+1和j+2位,如果是00的话显然根据题意,插头变成11,如果是11的话,明显插头变成00,然后01的话,新状态是10或者01,然后10类似。
      然后关于障碍物,障碍物需要转移的时候特判一下,如果那个格子是障碍物,那么第j位和第j+1位就不能是1。然后转移过来的状态那两位也不能为1。
      然后初始化的时候f[0][m][0]=1即可,从这个开始推。
      最后的答案就是f[n][m][0] 0.0

      PS:这一题实际上可以将三进制转化成四进制,只要四进制中的3不用就可以了,然后咱们就可以把这个四进制当做二进制的2位合并在一起来看,也就是说用二进制的2位来表示四进制的1位,这样子就可以使用位运算来优化速度。0v0
      PSS:这一题实际上可以使用二进制来表示,因为这里的左右插头实际上按照上面的讨论,咱们没有讨论插头是左还是右,所以这里只需要用是否有插头来表示即可。【这是由于题意中只与两个格子相连有关】
      PSSS:这一题换行的dp需要判断首位是否为1,首位判断为1需要位移M次,感觉非常不爽,所以咱们可以把状态表示倒过来,最高位表示最右边。这样只需要and 1一次即可。
      PSSSS:其实代码有抄袭嫌疑的233,希望当事人不要追究版权问题0.0

============================

program hdu1693;
var
  f:array[0..11,0..11,0..1 shl 12]of int64;
  a:array[0..11,0..11]of boolean;
  n,m,t:longint;

procedure init;
var i,j,k:longint;
begin
  read(n,m);
  for i:=1 to n do
   for j:=1 to m do
    begin
      read(k);
      a[i][j]:=k=1;
    end;
  fillchar(f,sizeof(f),0);
  f[0][m][0]:=1;
  for i:=1 to n do
   for j:=1 to m do
    if j=1 then
     begin
       if a[i][j] then
        for k:=0 to 1 shl m-1 do
         if k and 1=0 then
           f[i][j][k shl 1+3]:=f[i][j][k shl 1+3]+f[i-1][m][k]
         else
          begin
           f[i][j][k shl 1]:=f[i][j][k shl 1]+f[i-1][m][k];
           f[i][j][k shl 1-1]:=f[i][j][k shl 1-1]+f[i-1][m][k];
          end
       else
        for k:=0 to 1 shl m-1 do
          if k and 1=0 then f[i][j][k shl 1]:=f[i][j][k shl 1]+f[i-1][m][k];
     end
    else
     begin
       if a[i][j] then
        for k:=0 to 1 shl (m+1)-1 do
          if k and (1 shl (j-1))>0 then
            if k and (1 shl j)>0 then f[i][j][k-3 shl (j-1)]:=
            f[i][j][k-3 shl (j-1)]+f[i][j-1][k]
            else
             begin
               f[i][j][k]:=f[i][j][k]+f[i][j-1][k];
               f[i][j][k+1 shl (j-1)]:=f[i][j][k+1 shl (j-1)]+f[i][j-1][k];
             end
            else
             if k and (1 shl j)=0 then f[i][j][k+3 shl (j-1)]:=
             f[i][j][k+3 shl (j-1)]+f[i][j-1][k]
            else
             begin
               f[i][j][k]:=f[i][j][k]+f[i][j-1][k];
               f[i][j][k-1 shl (j-1)]:=f[i][j][k-1 shl (j-1)]+f[i][j-1][k];
             end
       else
        for k:=0 to 1 shl (m+1)-1 do
         if k and (3 shl (j-1))=0 then
           f[i][j][k]:=f[i][j][k]+f[i][j-1][k];
     end;
   writeln('Case ',t,': There are ',f[n][m][0],' ways to eat the trees.');
end;

begin
  read(t);
  for t:=1 to t do
    init;
end.


  评论这张
 
阅读(15)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017