P2831 愤怒的小鸟
斯德哥尔摩
2018-10-29 23:31:59
[P2831 愤怒的小鸟](https://www.luogu.org/problemnew/show/P2831)
看到$n\leq 18$，应该就想到状压$DP$了。
设$dp[s]$表示当前已经干掉的猪的压缩状态为$s$，所需要的最少的小鸟数。
然后可以得到方程：
$$\left.\begin{array}{}dp[0]=0\\dp[s|line[i][j]]=\min\{dp[s]+1\}\\dp[s|(1<<(i-1))]=\min\{dp[s]+1\}\end{array}\right.$$
复杂度$O(Tn^22^n)$。
乍一看，好像不会炸。。。
但是！当$n=18,T=5$时，就是$O(424673280)$！（别数了，$4$亿多。。。）
这不是铁定$TLE$嘛。。。
所以我们要想优化。
$No.1$：
我们发现当$i\in s,j\in s$时不用转移。
~~这不是废话么。。。~~
为什么呢？
如果这条线只经过至多三个点，因为其中一个点已被打到，所以可以通过另外两个点的状态转移。
如果$i,j$都被打到，则可以通过转移$3$（单独一个点）转移。
如果这条线经过多于三个点，则可以通过其它任选两个点转移。
优化了一波常数，但是核心复杂度并没有降下来。。。
$No.2$：
设$x$为满足$s\&(1<<(x-1))==0$的最小正整数，则由$S$扩展的转移的所有线都要经过$x$。
为什么？
我们想：先打$1,4$，再打$2,3$，和先打$2,3$，再打$1,4$，是不是一样的？
一样。
~~那不就行了？！~~
如果这一次转移不打$x$，那以后还要再回过头来打$x$。
于是这就是多余的转移。
因为经过$x$的线数量是$n$，所以每次转移涉及到的线就从$n^2$变成了$n$。
终于把核心复杂度降了下来。
所以只要预处理一下$[0,2^{18}]$的对应的$x$就可以了。
怎么预处理？
当然$O(n^3)$大暴力啊。。。
那，二次函数怎么办？
~~废话。。。~~
~~初三的知识别跟我说不会。。。~~
也就是求过$A(x_1,y_1),B(x_2,y_2)$两个点的二次函数$y=ax^2+bx$的方程。
那就暴力解方程嘛。。。
我们会解出来这个玩意：
$$a=\frac{x_2y_1-x_1y_2}{x_1x_2(x_1-x_2)}$$
$$b=\frac{y_1}{x_1}-\frac{x_2y_1-x_1y_2}{x_2(x_1-x_2)}=\frac{y_1}{x_1}-ax_1$$
然后带入即可。
到此，所有的问题都解决了。
总复杂度$O(Tn2^n)$了，这才是考场的正解。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#define MAXN 20
#define eps (1e-8)
using namespace std;
int n,S,special;
int line[MAXN][MAXN],lowestbit[1<<MAXN],dp[1<<MAXN];
struct Pig{
double x,y;
friend bool operator <(const Pig &p,const Pig &q){
if(p.x==q.x)return p.y<q.y;
return p.x<q.x;
}
}a[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void make(){//预处理
for(int i=0;i<(1<<18);i++){
int j;
for(j=1;j<=18&&(i&(1<<(j-1)));j++);
lowestbit[i]=j;
}
}
void init(){
n=read();special=read();
S=(1<<n);
for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);
sort(a+1,a+n+1);
memset(dp,127,sizeof(dp));
memset(line,0,sizeof(line));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){//暴力判二次函数
if(a[i].x==a[j].x)continue;
double A=(a[i].y*a[j].x-a[i].x*a[j].y)/(a[i].x*a[j].x*(a[i].x-a[j].x));
double B=a[i].y/a[i].x-a[i].x*A;
if(A>-eps)continue;
line[i][j]=(1<<(i-1))|(1<<(j-1));
for(int k=1;k<=n;k++){
if(i==k||j==k)continue;
double y=a[k].x*a[k].x*A+a[k].x*B;
if(fabs(y-a[k].y)<eps)line[i][j]|=(1<<(k-1));
}
}
}
void work(){
dp[0]=0;
for(int s=0;s<S;s++){
int i=lowestbit[s];
dp[s|(1<<(i-1))]=min(dp[s|(1<<(i-1))],dp[s]+1);
for(int j=1;j<=n;j++)dp[s|line[i][j]]=min(dp[s|line[i][j]],dp[s]+1);
}
printf("%d\n",dp[S-1]);
}
int main(){
int t=read();
make();
while(t--){
init();
work();
}
return 0;
}
```