洛谷2831 愤怒的小鸟

题意

有 $n(\le 18)$ 只绿猪，位置在 $(x_i,y_i)$ 。每次可以从 $(0,0)$ 发射一只小鸟，开口向下的抛物线上的猪会被消灭。问至少要发射多少只小鸟。

题解

容易想到暴力的状压。用 $f(S)$ 表示消灭集合 $S$ 中的绿猪需要多少只小鸟，预处理出经过 $i,j$ 两只猪的抛物线可以消灭的猪 $s[i][j]$，枚举不在 $S$ 中的两只猪 $i,j$ ，方程式为：

$$\begin{cases} f(S)+1\rightarrow f(S\cup s[i][j]) \\ f(S)+1\rightarrow f(S\cup i) \\ f(S)+1\rightarrow f(S\cup j) \end{cases}$$

时间复杂度 $O(2^nn^2)$ ，不能通过所有测试点，但已经可以取得相当可观的分数（85）。

考虑优化。可以发现枚举的猪中有一头，不妨设为 $i$ ，一定是最小的没在 $S$ 里的猪。这个可以感性理解，因为 $i$ 迟早都会被消灭，不如按顺序先消灭掉。这样就可以把时间复杂度降到 $O(2^nn)$ 。

求最小的没在 $S$ 中的猪可以先得到 $\mathrm{lowbit}(S)$ ，如果 $\mathrm{lowbit}(S)\neq 0$ ，那么就是 $\mathrm{lowbit}(S)-1$ ；否则就从 $\mathrm{lowbit}(S)$ 开始枚举找到第一个为 $0$ 的即可。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const double eps=1e-8;
const int inf=0x3f3f3f3f;
double x[19],y[19];
int t,n,m,f[1<<18],s[19][19],num[1<<18];

signed main()
{
    t=read();
    while (t--)
    {
        memset(s,0,sizeof(s));
        memset(f,0x3f,sizeof(f));
        n=read(); m=read();
        const int N=1<<n;
        for (int i=0;i<n;i++) num[1<<i]=i,f[1<<i]=1;
        for (int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);
        for (int i=2;i<=n;i++) for (int j=1;j<i;j++)
        {
            double x1=x[i]*x[i]*x[j],x2=x[j]*x[j]*x[i],y1=y[i]*x[j],y2=y[j]*x[i];
            double a=(y1-y2)/(x1-x2),b=(y[i]-a*x[i]*x[i])/x[i]; //解方程
            if (a>-eps) continue;
            for (int k=0;k<n;k++) if (fabs(a*x[k+1]*x[k+1]+b*x[k+1]-y[k+1])<eps) s[i][j]|=1<<k;
            f[s[j][i]=s[i][j]]=1;
        }
        for (int i=1;i<N;i++)
        {
            if (f[i]==inf) continue;
            int j=num[i&-i]; //lowbit
            if (j) j--;
            else for (;j<n && i>>j&1;j++);
            f[i|(1<<j)]=min(f[i|(1<<j)],f[i]+1);
            for (int k=0;k<n;k++) f[i|s[j+1][k+1]]=min(f[i|s[j+1][k+1]],f[i]+1);
        }
        printf("%d\n",f[N-1]);
    }
    return 0;
}