HDU 4901 The Romantic Hero

题目链接~~>

做题感悟：这题 dp 思路倒是好想，但是写的时候就手残了，结果一直wa ！！

解题思路：

                 因为相与的全在右边，抑或的全在左边，因此需要正向 dp 抑或一下，需要开三维的dpA [  i  ] [  S  ] [  k  ]  ( k = 0 , 1)  k = 0 ,代表前 i 个数达到状态 S 且没有选入第 i 个值所得到的最多的次数，k = 1 代表选入第 i 个数达到状态 S 所得到的最多次数  ，同样，需要逆向 dp 相与一下，dpB [  i  ] [  S  ] [  k  ]  ( k = 0 ,  1 ) , k = 0  ，代表逆向到达 i ,达到状态 S 且没选入第 i 个值所得到的最多次数 ， k = 1  , 代表逆向到达 i ,达到状态 S 且选入第 i 个值所得到的最多次数。

               最后，ans = ans + dpA[ i ] [ S ][ 1 ] * dpB[ i ] [ S ] [ 0 ]  ;  dpA 代表正向抑或包含 i 到达状态 S 的最多次数，dpB 代表逆向相与达到状态S 的最多次数。 

代码：

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<ctime>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      #include<cmath>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #define INT __int64
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const double esp = 0.00000001 ;
     
    
   

    

     

    
    

     

      const INT mod = 1e9 + 7 ;
     
    
   

    

     

    
    

     

      const INT MY = 1000 + 10 ;
     
    
   

    

     

    
    

     

      const INT MX = 2048 + 10 ;
     
    
   

    

     

    
    

     

      INT n ;
     
    
   

    

     

    
    

     

      INT g[MY] ;
     
    
   

    

     

    
    

     

      INT dpA[MY][MX][2] ,dpB[MY][MX][2] ;
     
    
   

    

     

    
    

     

      void DP()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 for(INT i = 1 ;i <= n ; ++i) // 正向抑或 dp
     
    
   

    

     

    
    

     
 for(INT S = 0 ;S <= 1024 ; ++S)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       dpA[i][S^g[i]][1] += (dpA[i-1][S][0] + dpA[i-1][S][1]) % mod ;
     
    
   

    

     

    
    

     

       dpA[i][S][0] = (dpA[i-1][S][0] + dpA[i-1][S][1]) % mod ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(INT i = n ;i >= 1 ; --i) // 逆向与 dp
     
    
   

    

     

    
    

     
 for(INT S = 0 ;S <= 1024 ; ++S)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       dpB[i][S&g[i]][1] += (dpB[i+1][S][0] + dpB[i+1][S][1]) % mod ;
     
    
   

    

     

    
    

     

       dpB[i][S][0] = (dpB[i+1][S][0] + dpB[i+1][S][1]) % mod ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       INT ans = 0 ;
     
    
   

    

     

    
    

     
 for(INT i = 1 ;i <= n ;i++) // 计算总的次数
     
    
   

    

     

    
    

     
 for(INT S = 0 ;S <= 1024 ; ++S)
     
    
   

    

     

    
    

     

       ans = (ans + (dpA[i][S][1]*dpB[i][S][0]) % mod) % mod ;
     
    
   

    

     

    
    

     
 cout<<ans%mod<<endl ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       INT Tx ;
     
    
   

    

     

    
    

     
 scanf("%I64d" ,&Tx) ;
     
    
   

    

     

    
    

     
 while(Tx--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%I64d" ,&n) ;
     
    
   

    

     

    
    

     
 memset(dpA ,0 ,sizeof(dpA)) ;
     
    
   

    

     

    
    

     
 memset(dpB ,0 ,sizeof(dpB)) ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%I64d" ,&g[i]) ;
     
    
   

    

     

    
    

     

       dpA[i][g[i]][1] = dpB[i][g[i]][1] = 1 ; // 只有一个数的时候
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       DP() ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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