【luogu P2831 愤怒的小鸟】 题解

题目链接：https://www.luogu.org/problemnew/show/P2831

写点做题总结：dp，搜索，重在设计状态，状态设的好，转移起来也方便。

对于一条抛物线，三点确定。(0,0)是固定的，所以我们一条抛物线要用两只猪确定。再多的猪就只能用来判断是不是在这条抛物线上了。

于是我们把猪分成两种：在已有方程里的猪，单独的猪还没有确定方程。

那么对于一只猪，就会有被以前方程覆盖/和前面单独的猪构成新抛物线/自己单独。

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

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;

}