当前位置：首页 -> AI编程基础 -> c++编程基础

SRM 574 D1L2：PolygonTraversal，dp

2014-11-24 10:10:31 · 作者: · 浏览: 1
标签: SRM 574 D1L2 PolygonTraversal

与上一题一样，只是限制条件变成了18，不能再用暴力法了，必须使用dp。

注意位操作，之前在isIntersect()函数中把 if ( mask & (1 << i) ) 写成了 if (mask >> i) ，这个bug调了很久才调出来。

代码：

#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 **********************/ long long dp[1 << 18][18]; class PolygonTraversal { public: int N, start, end; inline int addPoint(int mask, int p) { return ( mask | (1 << p) ); } bool isIntersect(int mask, int p1, int p2) { bool f1 = false, f2 = false; if (p1 > p2) { swap(p1, p2); } for (int i = 0; i < N; i++) { if ( mask & (1 << i) ) { if (i > p1 && i < p2) { f1 = true; } else if (i < p1 || i > p2) { f2 = true; } } } return f1 && f2; } long long rec(int mask, int p) { long long & res = dp[mask][p]; if (res != -1) { return res; } if (mask == end) { // base case if (isIntersect(mask, p, start) ) { res = 1; return 1; } else { res = 0; return 0; } } res = 0; for (int i = 0; i < N; i++) { if ( !( mask & (1 << i) ) ) { // 若点未访问 if (isIntersect(mask, p, i)) { // 若符合，加入该点 res += rec( addPoint(mask, i), i ); } } } return res; } long long count(int N, vector 
                          
                            points) { long long res = 0; this->N = N; end = (1 << N) - 1; start = points[0] - 1; int mask = 0; for (int i = 0; i < points.size(); i++) { --points[i]; mask = addPoint(mask, points[i]); } memset(dp, -1, sizeof(dp)); res = rec(mask, points[ points.size() - 1 ]); return res; } }; /************** Program End ************************/