题解 P2831 【愤怒的小鸟】

· · 题解 

/*
思路：

状压dp
预处理一个数组canshe[i][j]表示连接i,j两点做抛物线的时候能打到的小猪
特别的，canshe[i][i]只能打到自己，能打到的小猪分别是谁这个用二进制表示
然后进行dp
f[i|canshe[j][k]]=min(f[i|canshe[j][k]],f[i]+1)
但是这样只能得85分
需要优化一下 
当(i&(1<<(j-1))时，也就是说枚举的小猪之前打过，那么这种枚举之前以一定枚举过
所以我们只需要加上一个if(!(i&(1<<(j-1))))特判就能过 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const double eps=1e-8;
struct node{
    double x,y;
}pig[19];
int canshe[19][19];//用二进制表示  连接这两个点的抛物线能够打掉哪些点 
int f[1<<19];//表示打掉二进制位的当前状态的小鸟的最少花费 
int t,n,m; 
double a,b;
void calc(int x,int y)
{
    double xa=pig[x].x,ya=pig[x].y,xb=pig[y].x,yb=pig[y].y;
    double xaa=xa*xa,xbb=xb*xb;
    double op=xb/xa;
    xaa*=op;
    xa*=op;
    ya*=op;
    a=(ya-yb)/(xaa-xbb);
    b=(yb-a*xbb)/xb;
}
int main()
{
    freopen("angrybirds.in","r",stdin);
    freopen("angrybirds.out","w",stdout);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(canshe,0,sizeof(canshe));
        memset(f,0x3e,sizeof(f));
        f[0]=0;
        for(int i=1;i<=n;i++)
            scanf("%lf%lf",&pig[i].x,&pig[i].y);
        for(int i=1;i<=n;i++)
        {
            canshe[i][i]=1<<(i-1);
            for(int j=i+1;j<=n;j++)
            {
                calc(i,j);
                if(a>0)continue;
                for(int k=1;k<=n;k++)
                {
                    double ans=pig[k].x*a*pig[k].x+pig[k].x*b;
                    double tmp=ans-pig[k].y;
                    if(tmp<0)tmp=-tmp;
                    if(tmp<=eps)
                        canshe[i][j]|=(1<<(k-1));
                }
            }
        }
        for(int i=0;i<=(1<<n)-1;i++)
            for(int j=1;j<=n;j++)
                if(i&(1<<(j-1))==0)
                    for(int k=j;k<=n;k++)
                        f[i|canshe[j][k]]=min(f[i|canshe[j][k]],f[i]+1);
        printf("%d\n",f[(1<<n)-1]);
    }
    fclose(stdin);fclose(stdout);
    return 0;
}