参考了别人的博客

 

题意：先输入case数，每个case输入n，m，表示有n棵树，要用枪消灭m棵，下面n行给出n棵树的坐标，要求枪的个数最少。

DP状态压缩。原理是对于n棵树我们搞一个n位的二进制数，如果第i棵树还没有被消灭，在n位二进制数对应的位上就是1，否则为0。例如有5棵树，若11111，说明5棵树都没有被消灭；10101，说明第2,4棵树已经被消灭了，然后这个二进数再转为十进制，这个十进制数就是一个状态。我们可以真的开辟一个数组b[]来对应保存那些0,1，然后转化为十进制，但是知道原理之后我们利用c语言的位运算直接对十进制操作。

那我们要求的目标状态是什么？对于那个n位的二进制数，当1的个数小于等于（n-m）时，就不需要再消灭了，说明已经至少消灭了m棵。所以其实我们是在记忆化搜索过程中要这类状态的最小值。dp[ss]（ss是一个十进制数）,表示对于当前状态，最少需要多少把枪才能达到目的.显然最初的状态就是（2^n-1），( 即n位二进制数都是1，转化为十进制就是（2^n-1），表示所有树都还在，一棵都没有被消灭 ),一直递归搜索，一直到二进制数中1的个数小于等于n-m时就可以返回了。另外对于特殊的，但只剩下一个1的时候，就返回1，说明只有一棵树剩下时我们必须用一把枪消灭

另外，我们的目的是找出有多少棵树在一条直线上，找出多少个点在一条直线上，而且是哪几个点。首先判断a，b，c三点是否在一条直线只需要判断ab和ac的斜率是否相等，若相等则在一条直线上，因为它们过公共点a。

我们用s[i][j]来表示由第i和第j个点连接着成的直线，同样的s[i][j]也是 一个长度为n的二进制数，当对应的位上为1，则说明这些对应的点都在s[i][j]这条直线上，然后这个n位的二进制数再压成十进制数就可以了

然后就是记忆化搜索，对于当前的状态，枚举直线，然后消掉这个直线上的点到达下一个状态，直到目标状态为止。枚举直线的时候要注意，对于直线s[i][j],我们必须保证当前状态中第i，第j棵树还没有被砍掉

 

所以这个状态压缩有两处用到，都是长度为n的二进制数压成十进制数。

一处是表示那些树被砍掉那些树没有被砍掉时的状态，保存在f数组中。

另一处是对于表示直线的二维数组s[i][j]，表示那些树在这条直线上

 

 

#include 
     
      #include 
      
       #define INF 1000000000#define MAXN 20#define MAXS 1<<18int n,m,c;int x[MAXN],y[MAXN];int s[MAXN][MAXN];int f[MAXS];int dp(int ss){    int count,i,j,ans;    if(f[ss]!=-1)        return f[ss];    for(count=0,i=0; i
      
     

return f[ss];}void solve(int CASE){    int i,j,k,ans;    //进行状态压缩，记录在同一条直线上的点    memset(s,0,sizeof(s));    for(i=0; i
     
      =0; k--)                {                    s[i][j]<<=1;  //左移一位，为当前的点k腾出位置                    if( (y[j] - y[i]) * (x[k] - x[i]) == (y[k] - y[i])*(x[j] - x[i]) )                        s[i][j]++;   //其实相当于在长度为n的二进制的数对应的位置上标记1                    //其实是通过判断斜率来确定,原型为 (y[j]-y[i])/(x[j]-x[i]) == (y[k]-y[i])/(x[k]-x[i])                    //若相等可以容易证明i，j，k三点一线                    //写成乘法可以消掉特殊情况例如斜率为0或者斜率不存在等等                }            }        c=n-m;  //当剩下的树等于小于c的时候说明已经消灭完成        memset(f,-1,sizeof(f));        ans=dp( (1<