讲解 P2831 [NOIP2016 提高组] 愤怒的小鸟。

考虑状态压缩动态规划，需要根据两个点推出抛物线的解析式。

思路：

考虑先求出经过 \((x_1,y_1),(x_2,y_2)\) 的抛物线解析式

我们有：

\[\begin{cases} ax_1^2 + bx_1 = y_1 \\ ax_2^2 + bx_2 = y_2\end{cases}

\]

考虑将 \(b\) 消掉，求出 \(a\)。

那么考虑令 \(1\) 式减去 \(2\) 式的 \(\frac{x_1}{x_2}\) 倍：

\[ax_1^2 + bx_1 - ax_1x_2 - bx_1 = y_1 - \frac{x_1}{x_2} y_2

\]

\[a(x_1^2 -x_1x_2) = y_1 - \frac{x_1}{x_2} y_2

\]

\[a = \frac{y_1 - \frac{x_1}{x_2} y_2}{x_1^2 -x_1x_2} = \frac{y_1x_2 - x_1 y_2}{x_1^2x_2 - x_1x_2^2}

\]

因为 \(a\) 太复杂度，不好带入，考虑也将 \(a\) 消掉，求出 \(b\)。

那么考虑令 \(1\) 式减去 \(2\) 式的 \(\frac{x_1^2}{x_2^2}\) 倍：

\[ax_1^2 + bx_1 - ax_1^2 - b\frac{x_1^2}{x_2} = y_1 - y_2 \frac{x_1^2}{x_2^2}

\]

\[b(x_1 - \frac{x_1^2}{x_2}) = y_1 - y_2 \frac{x_1^2}{x_2^2}

\]

\[b = \frac{y_1 - y_2 \frac{x_1^2}{x_2^2}}{x_1 - \frac{x_1^2}{x_2}} = \frac{y_1x_2^2 - y_2 x_1^2}{x_1x_2^2 - x_1^2 x_2}

\]

那么我们可以得到经过 \((x_1,y_1),(x_2,y_2)\) 的抛物线解析式为：

\[y = \frac{y_1x_2 - x_1 y_2}{x_1^2x_2 - x_1x_2^2} x^2 + \frac{y_1x_2^2 - y_2 x_1^2}{x_1x_2^2 - x_1^2 x_2} x

\]

可以通过这个解析式求出其它在这个抛物线上的点，设 \(A_{i,j}\) 表示经过点 \(i\) 和点 \(j\) 的抛物线经过的所有点的点集。

考虑状态压缩 dp，令 \(dp_S\) 表示 \(S\) 这个点集的鸟被射下来的最小次数，则：

\[dp_0 = 0

\]

\[dp_{S \operatorname{or} A_{i,j}} = \min(dp_{S \operatorname{or} A_{i,j}},dp_S + 1)

\]

\[dp_{S \operatorname{or} 2^{i-1}} = \min(dp_{S \operatorname{or} 2^{i-1}},dp_S+1)

\]

时间复杂度为 \(O(Tn^22^n)\)。

完整代码：

<code>#include<bits/stdc++.h>

#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)

#define lowbit(x) x&(-x)

#define pi pair<ll,ll>

#define pii pair<ll,pair<ll,ll>>

#define iip pair<pair<ll,ll>,ll>

#define ppii pair<pair<ll,ll>,pair<ll,ll>>

#define fi first

#define se second

#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x

#define Full(a) memset(a,0,sizeof(a))

#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);

using namespace std;

typedef double db;

typedef unsigned long long ull;

typedef long long ll;

bool Begin;

const ll N=19,M=(1ll<<N)+10;

const db Eps=1e-6;

inline ll read(){

ll x=0,f=1;

char c=getchar();

while(c<'0'||c>'9'){

if(c=='-')

f=-1;

c=getchar();

}

while(c>='0'&&c<='9'){

x=(x<<1)+(x<<3)+(c^48);

c=getchar();

}

return x*f;

}

inline void write(ll x){

if(x<0){

putchar('-');

x=-x;

}

if(x>9)

write(x/10);

putchar(x%10+'0');

}

ll T,n;

ll a[N][N];

ll dp[M];

db x[N],y[N];

pair<db,db> get(db x1,db y1,db x2,db y2){

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

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

return {a,b};

}

db get(db x,db a,db b){

return a*x*x+b*x;

}

void solve(){

memset(dp,0x7f,sizeof(dp));

n=read(),read();

for(int i=1;i<=n;i++)

scanf("%lf%lf",&x[i],&y[i]);

for(int i=1;i<=n;i++){

for(int j=i+1;j<=n;j++){

a[i][j]=0;

auto t=get(x[i],y[i],x[j],y[j]);

if(t.fi>=0)

continue;

for(int k=1;k<=n;k++){

db h=get(x[k],t.fi,t.se);

if(abs(h-y[k])<=Eps)

a[i][j]|=(1ll<<(k-1));

}

}

}

dp[0]=0;

for(int S=0;S<(1ll<<n);S++){

for(int i=1;i<=n;i++){

for(int j=i+1;j<=n;j++){

if((a[i][j]&S)==a[i][j])

continue;

dp[S|a[i][j]]=min(dp[S|a[i][j]],dp[S]+1);

}

}

for(int i=1;i<=n;i++)

dp[S|(1ll<<(i-1))]=min(dp[S|(1ll<<(i-1))],dp[S]+1);

}

write(dp[(1ll<<n)-1]);

putchar('\n');

}

bool End;

int main(){

T=read();

while(T--)

solve();

cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";

return 0;

}