?

?

题目大意：给出n棵树的坐标，每次砍树能够将在同一直线上的树一起砍掉，然后给出要求你至少砍掉的树的数量，问你要达到这个要求需要砍多少次。

?

解题思路：因为这题的树的数量比较小（16）， 并且只有砍和不砍两种选择，可以用二进制数将状态表示出来。大致思路是：每次都将当前状态下的还没砍的树中选择两棵，在将和这两个树在同一直线上的树一起砍掉，得到新的状态。如果已经》=K棵了，就可以返回0了。一般来说，每次选择两棵树一起砍掉比较优，除非只剩下一棵树了。所以应该要先预处理出每两棵树和它们在同一直线上的树，并且这个状态可以也用二进制表示。

?

代码：

?

#include 
  
   
#include 
   
     const int maxn = 1<<17; const int M = 20; int dp[maxn]; int n, k; int tree[M][2]; int line[M][M]; bool judge (int i, int j, int k) { int a = (tree[j][1] - tree[i][1]) * (tree[k][0] - tree[j][0]); int b = (tree[k][1] - tree[j][1]) * (tree[j][0] - tree[i][0]); return a == b ? true : false; } int Min (const int a, const int b) { return a < b ? a: b; } void init () { for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { line[i][j] = 0; for (int l = 0; l < n; l++) { if (judge (i, j, l)) { line[i][j] |= (1<
    
     = k) return ans = 0; int flag = 0; for (int i = 0; i < n; i++) { if (((1 << i) & s) == 0) { for (int j = i + 1; j < n; j++) { if (((1 << j) & s) == 0) { flag = 1; ans = Min (ans, DP(s | line[i][j]) + 1); //printf (%d %d %d , s, s | line[i][j], ans); } } if (!flag) { ans = Min (ans, DP(s | (1<
     
      
?