NYOJ 492 King (状态压缩)

做题感悟：做完这题发现状态压缩有许多需要优化的地方。

解题思路：状态压缩

               开始自己用的一般的思路，就和炮兵阵地，郑厂长等题类似的方法做的，开始超时，然后把数组开到了最小的极限就险过。然后看了别人的代码感觉需要优化（注意）的地方太多了。

               首先我们这题可以预处理出来上下两行对应的合法状态，这样我们就确定下来上下两行对应的状态了，这是第一步的优化 。因为当前行只与上一行有关（这里只考虑当前行对上一行的影响就可以），我们可以把 dp 第一维开成 2 的就可以了，这是第二步的优化，虽然这步作用有点小。最后 ，我们还可以抛弃一些不合法的输入 ，假如是 n * n 的棋盘，一行最多可以防止（n+1）/ 2 个，然后 n 行最多可以放置 ( n + 1 ) / 2 * ( n + 1 ) / 2 个。 为什么是 ( n + 1 ) / 2 行放置呢 ？ 因为每个格子攻击相邻的八个格子，不要用n / 2 ,因为如果 奇数行的话就少算了一行。

               这题也可以用DFS递推和铺方格差不多，这样也相当于预处理出上下两行对应的状态。

代码：

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<cmath>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<bitset>
     
    
   

    

     

    
    

     

      #include<ctime>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<cctype>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std  ;
     
    
   

    

     

    
    

     

      #define INT long long int
     
    
   

    

     

    
    

     

      #define L(x) (x * 2)
     
    
   

    

     

    
    

     

      #define R(x) (x * 2 + 1)
     
    
   

    

     

    
    

     

      const int INF = 0x3f3f3f3f ;
     
    
   

    

     

    
    

     

      const double esp = 0.0000000001 ;
     
    
   

    

     

    
    

     

      const double PI = acos(-1.0) ;
     
    
   

    

     

    
    

     

      const int mod = 1e9 + 7 ;
     
    
   

    

     

    
    

     

      const int MY = 1400 + 5 ;
     
    
   

    

     

    
    

     

      const int MX = 150 ;
     
    
   

    

     

    
    

     

      int n ,m ,num ,top ;
     
    
   

    

     

    
    

     

      INT dp[2][MX][101] ;
     
    
   

    

     

    
    

     

      int key[MX] ,h[MX] ;
     
    
   

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int x ,y ,c ;
     
    
   

    

     

    
    

     

      }P[MY] ;
     
    
   

    

     

    
    

     

      void init() // 预处理合法状态
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 for(int S = 0 ;S < (1<<n) ; ++S)
     
    
   

    

     

    
    

     
 if(!(S&(S>>1)) && !(S&(S<<1)))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int nx = 0 ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < n ; ++i)
     
    
   

    

     

    
    

     
 if(S&(1<<i))
     
    
   

    

     

    
    

     

       nx++ ;
     
    
   

    

     

    
    

     

       key[num] = S ;
     
    
   

    

     

    
    

     

       h[num++] = nx ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 while(~scanf("%d%d" ,&n ,&m))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(((n+1)/2)*((n+1)/2) < m)  // 抛弃不合法的状态
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 puts("0") ;
     
    
   

    

     

    
    

     
 continue ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       num = 0 ;  top = 0 ;
     
    
   

    

     

    
    

     

       init() ; // 预处理合法状态
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < num ; ++i)  // 预处理上下两行对应的合法状态
     
    
   

    

     

    
    

     
 for(int j = 0 ;j < num ; ++j)
     
    
   

    

     

    
    

     
 if(!(key[i]&(key[j]>>1)) && !(key[i]&(key[j]<<1)) && !(key[i]&key[j]))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       P[top].x = i ;
     
    
   

    

     

    
    

     

       P[top].y = j ;
     
    
   

    

     

    
    

     

       P[top++].c = h[j] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 memset(dp[0] ,0 ,sizeof(dp[0])) ;
     
    
   

    

     

    
    

     

       dp[0][0][0] = 1 ;
     
    
   

    

     

    
    

     
 for(int i = 1 ;i <= n ; ++i)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 memset(dp[i&1] ,0 ,sizeof(dp[i&1])) ;
     
    
   

    

     

    
    

     
 for(int j = 0 ;j < top ; ++j) // 上一行的合法状态
     
    
   

    

     

    
    

     
 for(int t = 0 ;t <= m ; ++t) // 安放的个数
     
    
   

    

     

    
    

     
 if(t + P[j].c <= m) // 个数限制
     
    
   

    

     

    
    

     

       dp[i&1][P[j].y][t+P[j].c] += dp[(i+1)&1][P[j].x][t] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       INT ans = 0 ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < num ; ++i)
     
    
   

    

     

    
    

     

       ans += dp[n&1][i][m] ;
     
    
   

    

     

    
    

     
 printf("%lld\n" ,ans) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/40142521