题目链接：http://lightoj.com/volume_showproblem.php?problem=1018
题目描述：
有n个点，问最少用几条无线长的线段把这n个点全部覆盖起来？
解题思路：
其实应该换一种枚举方式，先预处理出来每条线段，对每一个状态选择两个不在状态的点，然后画以两个点为端点的线，来进行状态转移。这个题目最重要的优化在于如何挑选不在状态的两个点，测试实力比较多，我们可以预处理出来每个状态未覆盖的点。
1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cstdio> 6 #include <vector> 7 #include <ctime> 8 #include <queue> 9 #include <list> 10 #include <set> 11 #include <map> 12 using namespace std; 13 #define INF 0x3f3f3f3f 14 typedef long long LL; 15 16 int x[20], y[20], dp[1<<16], line[20][20]; 17 vector <int> p[1<<16]; 18 void init() 19 { 20 for(int i = 0; i < (1<<16); i++) 21 { 22 for(int j = 0; j < 16; j++) 23 { 24 if((i & (1<<j))) 25 continue; 26 p[i].push_back(j); 27 } 28 } 29 } 30 int check(int i, int j, int k) 31 { 32 int y2 = y[j], y1 = y[i], y3 = y[k]; 33 int x2 = x[j], x1 = x[i], x3 = x[k]; 34 if(y3*(x2-x1)==(y2-y1)*x3+x2*y1-x1*y2) 35 return 1; 36 else 37 return 0; 38 //return (y2-y1)*(x3-x2) == (y3-y2)*(x2-x1); 39 } 40 int main() 41 { 42 int t, n; 43 scanf("%d", &t); 44 init(); 45 for(int ca = 1; ca <= t; ca++) 46 { 47 scanf("%d", &n); 48 for(int i = 0; i < n; i++) 49 scanf("%d %d", &x[i], &y[i]); 50 memset(line, 0, sizeof(line)); 51 for(int i = 0; i < n; i++) 52 { 53 line[i][i] = (1<<i); 54 for(int j = i+1; j < n; j++) 55 { 56 for(int k = 0; k < n; k++) 57 { 58 if(check(i, j, k)) 59 line[i][j] |= (1<<k); 60 } 61 } 62 } 63 memset(dp, INF, sizeof(dp)); 64 dp[0] = 0; 65 for(int i = 0; i < (1<<n) -1; i++)//这里一定要减1，不然会re,我re了n发 = = 66 { 67 int x = p[i][0]; 68 for(int j = 0; j < p[i].size(); j++) 69 { 70 int y = p[i][j]; 71 dp[i|line[x][y]] = min(dp[i|line[x][y]], dp[i]+1); 72 } 73 } 74 printf("Case %d: %d ", ca, dp[(1<<n)-1]); 75 } 76 return 0; 77 }