题目大意：在平面直角坐标系中，给定\(n\)个点的坐标，要求删去其中\(m\)个点，每次可以将一条直线上所有点删去，问最少的操作次数。
\(P.s.:\)每个测试点有\(T\)组测试数据,且满足\(0 \leq m \leq n \leq 16,0 \leq T \leq 20\).
很显然，看到题目的数据范围\(0 \leq m \leq n \leq 16\)，就应该想到这在疯狂提示我们：
状压！ 状压！！ 状压！！！
那么，此题我们采用状态压缩 \(+\) 记忆化搜索的方法。
我们用二进制数来表示状态，例如\(10010\)表示第\(2,3,5\)个点应经被删去了，我们用\(f[i]\)来表示到达\(i\)这个状态所需最少次数，用于记忆化，\(g[i][j]\)同样储存二进制状态，表示经过\(i,j\)两点的直线能删去的点的个数，在\(g[i][j]\)中，\(10010\)表示第一个点和第四个点在一条直线上。
在记录有几个点在一条直线上时，我们根据两点斜率是否相等来判断，同时对于三个点\((x_i,y_i),(x_j,y_j),(x_k,y_k)\),我们这样来判断斜率是否相等：
\((x_j-x_i) * (y_k-y_j) == (y_j-y_i) * (x_k-x_j)\)
这样就避免了斜率为正无穷的情况。
接下来进行记忆化搜索即可，对于当前状态，我们枚举直线来到达下一状态，直至到达目标状态为止。
具体细节看代码实现：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 70000;
int T, n, m, x[20], y[20], g[20][20]; //x，y储存坐标，g用于储存直线
int f[maxn], N;
// f用于记忆化，N为初始状态。
void init()
{
memset(f, -1, sizeof(f));
memset(g, 0, sizeof(g)); //多测不清空，爆零两行泪！！！
scanf("%d%d", &n, &m);
N = (1 << n) - 1; //搜索初始状态
for (int i = 0; i < n; i++)
scanf("%d%d", &x[i], &y[i]);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
for (int k = n - 1; k >= 0; k--) {
g[i][j] <<= 1; //左移一位，为下一个点腾出位置
if ((x[j] - x[i]) * (y[k] - y[j]) == (y[j] - y[i]) * (x[k] - x[j]))
g[i][j]++; //表示这个点在这条直线上
}
}
}
}
int Count(int k)
{
int cnt = 0;
for (int i = 0; i < n; i++)
if ((1 << i) & k) cnt++;
return cnt;
}
int dfs(int now)
{
int cnt = Count(now);
// Count用于计算还有多少个点没删
int& ans = f[now];
// 这个取地址符一定要加！！ 原因是后面f[now]也要改变
if (cnt <= n - m) return ans = 0;
// 如果剩下的点小于n-m，那么就不用再删了，直接返回0
else if (cnt == 1) return ans = 1;
//如果还剩一个点，直接用一条直线来删
else if (ans > -1) return ans;
//记忆化，不解释
ans = (1 << 30);
//都没有，枚举直线更新状态
for (int i = 0; i < n; i++) {
if ((1 << i) & now) {
// 保证i这个点还没有被删
for (int j = i + 1; j < n; j++) {
if ((1 << j) & now) {
//保证j这个点没被删
int temp = now & (g[i][j] ^ N); //异或取补集，再取and，得到下一个状态
ans = min(ans, dfs(temp) + 1); //更新ans
}
}
}
}
return ans;
}
int main()
{
int t = 1;
scanf("%d", &T);
while (T--) {
init(); //初始化
printf("Case #%d:\n%d\n", t++, dfs(N));
if (T) puts("");
}
return 0;
}
此题和NOIP2016 愤怒的小鸟大同小异，建议大家可以去康一康，算是一道比较基础的状压dp题目。
任何不懂请私信本人或发讨论区，本人会定期来康。
update：
大家应该看到了评论中的hack数据，没错，我被hack了……
原因是这组hack数据中有两个点重复了，所以我的代码出现了错误，确实题目并未说明点不重复，在此，感谢 @Flandre_495 指出错误。
那么，我们其实只需要在枚举直线时加上判重的语句就可避免这个问题。
给出修正部分代码片段：
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
if (x[i] == x[j] && y[i] == y[j]) continue;
for (int k = n - 1; k >= 0; k--) {
g[i][j] <<= 1; //左移一位，为下一个点腾出位置
if ((x[j] - x[i]) * (y[k] - y[j]) == (y[j] - y[i]) * (x[k] - x[j]))
g[i][j]++; //表示这个点在这条直线上
}
}
}完结撒花o(≧v≦)o