斯德哥尔摩 的博客

斯德哥尔摩 的博客

P2831 愤怒的小鸟

posted on 2018-10-29 23:31:59 | under 刷题 |

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)$了,这才是考场的正解。

附代码:

#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;
}