题目链接：
写点做题总结：dp，搜索，重在设计状态，状态设的好，转移起来也方便。
对于一条抛物线，三点确定。(0,0)是固定的，所以我们一条抛物线要用两只猪确定。再多的猪就只能用来判断是不是在这条抛物线上了。
于是我们把猪分成两种：在已有方程里的猪，单独的猪还没有确定方程。 那么对于一只猪，就会有被以前方程覆盖/和前面单独的猪构成新抛物线/自己单独。#include#include #include #include #include using namespace std;const int maxn = 20;const int INF = 0x7fffffff;const double eps = 1e-8;int n, m, ans, T;double x[maxn], y[maxn], a[maxn], b[maxn], xx[maxn], yy[maxn];void dfs(int c, int u, int v)//搜当前第c个，前面构造好了u个方程，单独的猪v个 { if(u + v >= ans) return; if(c > n) { ans = min(u + v, ans); return; } bool flag = 0; for(int i = 1; i <= u; i++)//被之前的经过 { if(fabs(a[i]*x[c]*x[c] + b[i]*x[c] - y[c]) < eps) { dfs(c+1, u, v); flag = 1; break; } } if(!flag)//之前的不经过 { for(int i = 1; i <= v; i++)//在前面找一个单独的构成抛物线 { if(fabs(xx[i] - x[c]) < eps) continue; double nowa = (y[c]*xx[i]-x[c]*yy[i])/(x[c]*xx[i]*(x[c]-xx[i]));//计算这个抛物线 double nowb = (xx[i]*xx[i]*y[c]-x[c]*x[c]*yy[i])/(x[c]*xx[i]*(xx[i]-x[c])); if(nowa < 0) { a[u+1] = nowa, b[u+1] = nowb; double nowx = xx[i], nowy = yy[i]; for(int j = i; j < v; j++) { xx[j] = xx[j+1]; yy[j] = yy[j+1]; } dfs(c+1, u+1, v-1); for(int j = v; j > i; j--) { xx[j] = xx[j-1]; yy[j] = yy[j-1]; } xx[i] = nowx; yy[i] = nowy; } } xx[v+1] = x[c], yy[v+1] = y[c]; dfs(c+1, u, v+1); }}int main(){ scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++) scanf("%lf%lf",&x[i],&y[i]); ans = INF; dfs(1, 0, 0); printf("%d\n",ans); } return 0;}