题目链接：点击进入 最多只有16个点，如果不用状态压缩的话，最优子结构没法找到。所以我们进行状态压缩，用一个数表示当前的状态，对应二进制位为1表示该位置的树还未被砍掉，为0表示已被砍掉，初始状态为2^n-1；然后状态转移就是选两颗树作为此次要砍掉直线的两端。另外我们也需要提前处理出任意两棵树连成直线上有多少树的情况，，这个也可以用相似的二进制压缩思想。
代码如下：
;{ int x,y;}P;P p[maxn];int dp[(1<<maxn)+10],n,m;int cnt[1<<maxn],s[maxn][maxn];int check(int i,int j,int k){return (p[i].y-p[j].y)*(p[j].x-p[k].x)==(p[i].x-p[j].x)*(p[j].y-p[k].y);}int Count(int x){int num=0;while(x){num++;x=x&(x-1);}return num;}int dfs(int x){if(dp[x]!=-1) return dp[x];if(cnt[x]<=n-m) return dp[x]=0;if(cnt[x]==1) return dp[x]=1; ///要注意只剩一个点的情况int tmp=INF;for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){if(((1<<i)&x)&&((1<<j)&x)){int t=dfs(x&s[i][j]);if(t+1<tmp)tmp=t+1;}}return dp[x]=tmp;}int main(){int t,Case=0;freopen(“in.txt”,”r”,stdin);scanf(“%d”,&t);while(t–){scanf(“%d%d”,&n,&m);for(int i=0;i<n;i++)scanf(“%d%d”,&p[i].x,&p[i].y);for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)s[i][j]=(1<<n)-1;for(int i=0;i<=(1<<n)-1;i++)cnt[i]=Count(i);for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)for(int k=0;k<n;k++)if(check(i,j,k))s[i][j]-=(1<<k);memset(dp,-1,sizeof(dp));int ans=dfs((1<<n)-1);printf(“Case #%d:\n%d\n”,++Case,ans);if(t) printf(“\n”);} return 0;}
一个积极奋进的目标，一种矢志不渝的追求。
