UVA 11008 Antimatter Ray Clearcutting

题目链接~~>

做题感悟：这题最开始的想法是先处理一下在同一条直线上的点用二进制压缩一下，然后用背包处理一下，但是超时了 ，后来看了别人写的才知道原来这样也可以，但是我在去除一条线段上的点的时候用抑或做的，这样是不行的，如果是单独一个点的话就可以。

解题思路：记忆化 + 状态压缩

              这题第一感觉是要把同一条直线上的点用二进制压缩一下，那么，同一条直线上的点怎样压缩呢 ？ 可以用key[ i ] [  j ] 记录在直线 i  , j 上有多少点存在，这样如果想打掉这条直线的话，就一同打掉在直线上所有的点，判断是否在 i , j 直线上时比较一下斜率就可以了，这里要用乘法判断斜率相等，这样就避免了斜率是正无穷的那种情况，这样第一步就算完成了。

            接下来就是记忆化搜索了，这里用记忆化搜索比较方便也比较好想，开始当然是一棵树也没有砍掉，传递 （1<<n）-1 ,那么，dp[ S ] 代表到达 S 状态是最少要砍几次，其中 S中二进制位上0 的个数代表已经砍掉几棵树，从而如果 S 中 0 （即 1 的个数不大于 n-m） 的个数大于等于 m 时，就不需要继续砍树了，还有一种特殊情况：如果只有一棵树那么久只需要一次就可以了，so~>返回 1 .

代码：

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<ctime>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #define INT long long int
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const double esp = 0.00000001 ;
     
    
   

    

     

    
    

     

      const int INF = 1000000000 ;
     
    
   

    

     

    
    

     

      const int MY = 20 ;
     
    
   

    

     

    
    

     

      const int MX = (1<<17) + 10 ;
     
    
   

    

     

    
    

     

      int n ,m  ;
     
    
   

    

     

    
    

     

      int dp[MX] ,key[MY][MY] ,a[MY] ,b[MY] ;
     
    
   

    

     

    
    

     

      int DP_Memory(int S)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(dp[S] != -1) return dp[S] ;
     
    
   

    

     

    
    

     
 int cnt = 0 ;
     
    
   

    

     

    
    

     
 int& ans = dp[S] ;
     
    
   

    

     

    
    

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

    

     

    
    

     
 if(S &(1<<i))
     
    
   

    

     

    
    

     

       cnt++ ;
     
    
   

    

     

    
    

     
 if(cnt <= n-m)  return ans = 0 ;
     
    
   

    

     

    
    

     
 if(cnt == 1)  return ans = 1 ;
     
    
   

    

     

    
    

     

       ans  = INF ;
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     
 if((S &(1<<i)) && (S &(1<<j)))
     
    
   

    

     

    
    

     

       ans = min(ans ,DP_Memory(S &(~key[i][j]))+1) ;// 切记不要用抑或处理！！
     
    
   

    

     

    
    

     
 return ans ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void init()// 处理两点构成的直线上有包含点
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 memset(key ,0 ,sizeof(key)) ;
     
    
   

    

     

    
    

     
 memset(dp ,-1 ,sizeof(dp)) ;
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     
 if((b[j]-b[i])*(a[k]-a[i]) == (b[k]-b[i])*(a[j]-a[i]))
     
    
   

    

     

    
    

     

       key[i][j] |=(1<<k) ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int Tx ,cse=1 ;
     
    
   

    

     

    
    

     
 scanf("%d",&Tx) ;
     
    
   

    

     

    
    

     
 while(Tx--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d",&n ,&m) ;
     
    
   

    

     

    
    

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

    

     

    
    

     
 scanf("%d%d",&a[i] ,&b[i]) ;
     
    
   

    

     

    
    

     

       init() ;
     
    
   

    

     

    
    

     
 cout<<"Case #"<<cse++<<":"<<endl ;
     
    
   

    

     

    
    

     
 cout<<DP_Memory((1<<n)-1)<<endl ;
     
    
   

    

     

    
    

     
 if(Tx)  cout<<endl ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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