【洛谷 P2831】 愤怒的小鸟【状态压缩】

解题思路

预处理一个 st[i][j] 表示经过 i,j 两点的抛物线能经过的所有点的集合，具体做法就是枚举出两个点，分别算出对应的a,b，然后再枚举点，判断是否再当前线上出现过。

如何求a,b:

设dp[S]表示以被消灭的状态为S时，需要多少只鸟。
一个奇妙的初始化 v [ i ] v[i] v[i]，存的是是 i i i这个状态内第一个0的位置，也就是我们做dp的起始位置。

首先，我们开始操作的点是start[i]，我们先将它预先转移一下，s=start[i]，假设s这头猪被打掉的状态等于i被打掉的状态的最小抛物线数，和目前i没被打掉状态直接加一只打掉i。

代码

#include
#include
#include
#include
#include
#include
#define ll long long
#define db double
using namespace std;

const double e=1e-6;
int T,n,m,st[20][20],v[1<<19],dp[1<<19];
double a[20],b[20],x,y;

void work(db x1,db y1,db x2,db y2) {
	x=(y2*x1-y1*x2)/(x2*x2*x1-x1*x1*x2);
	y=(y1*x2*x2-y2*x1*x1)/(x1*x2*x2-x2*x1*x1);
}

int main() {
	for(int i=0; i<=(1<<18); i++) {
		int j=1;
		for(; j<=18&&i&(1<-e)continue;
				for(int k=1; k<=n; k++) {
					if(fabs(a[k]*a[k]*x+y*a[k]-b[k])