P2831 愤怒的小鸟

题面:https://www.luogu.org/problem/P2831

本题可以预处理出i,j两点经过的抛物线能经过的所有点的集合,
然后设dp[S]表示已经死了的猪的集合状态为S时最少要发射的鸟数
转移时还有一个优化就是每次从第一个没有被打过的鸟开始打,因为如果从后面开始打还要回来打这只鸟,降低了算法效率.

Code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<ctime>
using namespace std;
const double eps=1e-6;
const int N=22,M=1<<22;
int t,n,m,lines[N][N],lowunbit[M],dp[M],pos[M];
double x[N],y[N];
void equation(double &x,double &y,double a1,double b1,double c1,double a2,double b2,double c2){
    y=(a1*c2-a2*c1)/(a1*b2-a2*b1);
    x=(c1-b1*y)/a1;
}
int main(){
    memset(pos,-1,sizeof(pos));
    for(int i=0;i<(1<<20);i++){
        for(int j=1;j<=20;j++){
            if(!(i&(1<<(j-1)))){
                pos[i]=j;
                break;
            }
        }
    }
    scanf("%d",&t);
    while(t--){
        memset(lines,0,sizeof(lines));
        memset(dp,0x3f,sizeof(dp));
        dp[0]=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%lf%lf",&x[i],&y[i]);
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                if(fabs(x[i]-x[j])<eps){
                    continue;
                }
                double a,b;
                equation(a,b,x[i]*x[i],x[i],y[i],x[j]*x[j],x[j],y[j]);
                if(a>-eps){
                    continue;
                }
                for(int k=1;k<=n;k++){
                    if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<eps){
                        lines[i][j]|=(1<<(k-1));
                    }
                }
            }
        for(int i=0;i<(1<<n);i++){
            int j=pos[i];
            if(j==-1){
                continue;
            }
            for(int k=j;k<=n;k++){
                if(j==k){
                    dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]+1);
                }
                if(fabs(x[j]-x[k])<eps){
                    continue;
                }
                dp[i|lines[j][k]]=min(dp[i|lines[j][k]],dp[i]+1);
            }
        }
        printf("%d\n",dp[(1<<n)-1]);
    }
    return 0;
}

P2831 愤怒的小鸟

原文：https://www.cnblogs.com/ukcxrtjr/p/11521866.html