SRM 601 D1 L2：WinterAndSnowmen， dp - c++编程基础

先尝试简单dp方法，时间复杂度O( max(N, M)^3 )，此方法只能求解 max(N, M)不超过200的情况，如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include
                 #include 
                 
                   #include 
                  
                    #include 
                   
                     #include 
                    
                      #include 
                     
                       #include 
                      
                        #include 
                       
                         using namespace std; #define CHECKTIME() printf(%.2lf , (double)clock() / CLOCKS_PER_SEC) typedef pair
                        
                          pii; typedef long long llong; typedef pair
                         
                           pll; #define mkp make_pair /*************** Program Begin **********************/ const int MOD = 1e9 + 7; int dp[200][200][200]; class WinterAndSnowmen { public: int N, M; int rec(int t, int x, int y) { if (t == 0) { if (x < y) { return 1; } else { return 0; } } int & res = dp[t][x][y]; if (res != -1) { return res; } res = 0; if (t <= N) { res += rec(t - 1, x ^ t, y); res %= MOD; } if (t <= M) { res += rec(t - 1, x, y ^ t); res %= MOD; } res += rec(t - 1, x, y); res %= MOD; return res; } int getNumber(int N, int M) { this->N = N; this->M = M; memset(dp, -1, sizeof(dp)); return rec(max(N, M), 0, 0); } }; /************** Program End ************************/

按 Editorials 中给的方法进行优化，得到O( max(N, M) ^ 2 )，最后的optimizations一定也要做，要不然还是会超时，如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include
                 #include 
                 
                   #include 
                  
                    #include 
                   
                     #include 
                    
                      #include 
                     
                       #include 
                      
                        #include 
                       
                         using namespace std; #define CHECKTIME() printf(%.2lf , (double)clock() / CLOCKS_PER_SEC) typedef pair
                        
                          pii; typedef long long llong; typedef pair
                         
                           pll; #define mkp make_pair /*************** Program Begin **********************/ const int MOD = 1e9 + 7; const int MAX_BITS = 11; const int MAX_N = 2000; int dp[MAX_N + 1][1 << MAX_BITS][2]; class WinterAndSnowmen { public: int p, N, M; inline int getBit(int z, int p) { return ( (z >> p) & 1 ); } int rec(int t, int z, int b) { if (0 == t) { if ( 0 == b && 1 == z ) { return 1; } else { return 0; } } int & res = dp[t][z][b]; if (res != -1) { return res; } res = 0; if (t <= N) { res += rec(t - 1, z ^ (t >> p), b ^ getBit(t, p)); res %= MOD; } if (t <= M) { res += rec(t - 1, z ^ (t >> p), b); res %= MOD; } res += rec(t - 1, z, b); res %= MOD; return res; } int getNumber(int N, int M) { this->N = N; this->M = M; int res = 0; for (p = 0; p < 11; p++) { memset(dp, -1, sizeof(dp)); res += rec( max(N, M), 0, 0 ); res %= MOD; } return res; } }; /************** Program End ************************/