插头DP。对于本题我们只需要记录之前\(m\)个格子的\(m+1\)个插头是否存在。

转移时根据左边、上边是否有插头讨论。用位运算可以写的很方便。

因为想对DP数组压压维，我也觉得写的好不直观=-=。反正就是从上一个格子转移，解决完一行将状态左移一位转给下一行。要看直观的代码可以看上面链接里的代码...

最简单的插头DP...反正我也是做过插头DP的人了233

//0MS   1260K#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define gc() getchar()typedef long long LL;const int N=12;LL f[2][(1<
        
         >y-1&1)!=(s>>y&1)) f[s]+=g[s];        }    else        for(int s=0,p1=1<
         
          <