P2831 愤怒的小鸟

从 \((0, 0)\) 发射一只鸟， 轨迹满足抛物线， 问最少几只鸟可以打完 \(n <= 18\) 只猪

---

错误日志： 处理抛物线数组没有初始化

---

Solution

数据范围识状压

挺好想的状压dp

对于每只猪考虑两种情况： 自己被单独打下来或者被其他抛物线经过打下来

现在已经有一个确定点 \((0 ,0)\) 再加一只猪， 两个点无法确定一条抛物线

也就是说这条抛物线是可以给你自己规划的

也也就是说自己被单独打下来一定可行

不过能打多一点会更优

三点确定抛物线

我们暴力枚举两只没被打下来的猪

看还能打几只

更新dp即可

注意两点：

预处理出所有抛物线能打几只猪， 可以省一维枚举每只猪， 不然 \(TLE\)

此题卡精度， 判断两个浮点数是否相等可以确定一个精度 （此题设置为 \(10^{-6}\)）

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<climits>

#include<cmath>

#define LL long long

#define REP(i, x, y) for(int i = (x);i <= (y);i++)

using namespace std;

int RD(){

    int out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const int maxn = (1 << 19);

int T;

int num;

int dp[maxn], one[25];

double a, b;

inline void build(double &a,double &b,double x1,double y1,double x2,double y2){

    a=(x2*y1-x1*y2)/(x1*x2*(x1-x2));

    b=(x1*x1*y2-x2*x2*y1)/(x1*x2*(x1-x2));

	}//计算a,b

bool judge(double x, double y){

	double y1 = a * x * x + b * x;

	if(fabs(y - y1) <= 1e-6)return 1;

	return 0;

	}

struct Node{

	double x, y;

	}I[25];

int van[25][25];

void init(){

	memset(van, 0, sizeof(van));

	REP(i, 1, num){

		REP(j, i + 1, num){

			if(fabs(I[i].x - I[j].x) <= 1e-6)continue;

			build(a, b, I[i].x, I[i].y, I[j].x, I[j].y);

			if(a >= 0)continue;

			REP(k, 1, num){

				if(judge(I[k].x, I[k].y))van[i][j] |= one[k];

				}

			}

		}

	}

int main(){

	T = RD();

	while(T--){

		num = RD(), RD();

		REP(i, 1, num)scanf("%lf %lf", &I[i].x, &I[i].y), one[i] = (1 << (i - 1));

		int maxstate = (1 << num) - 1;

		REP(i, 0, maxstate)dp[i] = 1e9;

		init();

		dp[0] = 0;

		REP(i, 0, maxstate){//状态

			REP(j, 1, num){//一只新猪

				if(i & one[j])continue;

				dp[i | one[j]] = min(dp[i | one[j]], dp[i] + 1);//看看只打一只猪赚不赚

				REP(k, j + 1, num){//另一只新猪

					if(i & one[k] || !van[j][k])continue;

					dp[i | van[j][k]] = min(dp[i | van[j][k]], dp[i] + 1);

					}

				}

			}

		printf("%d\n", dp[maxstate]);

		}

	return 0;

	}