状态压缩DP

18 Oct 2017

Reading time ~1 minute

状态压缩DP

愤怒的小鸟

第一次接触状态压缩DP是在NOIP2016的愤怒的小鸟，当时菜得连题目都没看懂，不过现在回过头来看还是挺简单的，那么我们再来看看这道题吧。

题意&数据范围看这

考虑预处理出两个点构成的抛物线，因为经过原点，所以对于二次函数

$ax^2+bx+c 有 c=0$

因此已知两个点 $(x_1,y_1),(x_2,w_2)$ 可得出

$a={ { {y_2 \over x_2} - {y_1 \over x_1} } \over {x_2-x_1}}$ $b={ {y_2 - {ax_2^2} } \over {x_2}}$

所以思路也就自然而然的来了,枚举两个点，求出它们所构成的抛物线，再枚举其它的点，看这条抛物线经过另外的哪些点。

然后问题又来了，该如何存储这条抛物线上的信息？

思路1：储存这条抛物线上的个数

这应该是最好想到的一条思路了，但也很快可以否决掉，会发现只存个数的话会无法判断是否打完。

思路2：对每条抛物线开一个数组

这样做的正确性无法否定，可是你的空间呢？

思路3：二进制信息存储

有的时候暴力的思想也是很重要的，这往往预示着正解。

既然我们只要表示某个点的存在或否，我们何不用2进制的一位来表示呢？

这便是状态压缩的核心思想了，对于简单的状态存储，重新开数组太过浪费，可以用一个二进制数来代替数组。

假设我们现在有5个点，那么一条抛物线的初始状态是什么也没有，用一个五位的二进制数表示即 00000。

现在假设我们发现第3个点在这条抛物线上，即要让它变成00100 要怎么办呢。

不难想到我们只要把 1 左移 2 位，再or上去就行了。

因此每当我们发现一个编号为 $i$ 的点，假设表示抛物线的数为 $f$ ,那么我们可以写出如下运算式:

$f= f \mid ( 2 ^ {i-1} )$

这样就可以预处理出所有的抛物线了，

然后有了抛物线，状态转移方程也不难写出来。

$设dp_i表示当前状态最小需要的最小猪，则:$ $dp_{i|f}=min\{dp_i+1\} 其中f为抛物线。$

#include<cstdio>
#include<cstring>
#include<cmath>
#define maxm 1000+10
#define maxn 1000+10
#define min(a,b) (a<b?a:b)
using namespace std;
int f[(1<<20)],get[20][20];
double x[20],y[20];
template<class T>
inline bool read(T&n,char ch=getchar(),int sign=1){
    if(ch==EOF)return 0;for(n=0;(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
    if(ch=='-')sign=-1,ch=getchar();for(;ch>='0'&&ch<='9';ch=getchar())
    (n*=10)+=(ch-'0');n*=sign;return 1;
}
inline bool equ(double a,double b){
    return abs(a-b)<10e-8;
}
int main(){
    #ifdef Files
        freopen("f.in","r",stdin);
        freopen("f.out","w",stdout);
    #endif
    #ifdef die
    for(int i=1;i<=19;i++) printf("%d ",un[i]);
    #endif
    int T;read(T);
    for(int i=1;i<=T;i++){
        int n,m,tot=0;read(n),read(m);
        memset(get,0,sizeof(get));
        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++){
                if(equ(x[i],x[j]))continue;
                double a=(y[j]/x[j]-y[i]/x[i])/(x[j]-x[i]);
                 double b=(y[j]-a*x[j]*x[j])/x[j];
                if(a>-1e-8) continue;
                for(int k=1;k<=n;k++)
                    if(equ(a*x[k]*x[k]+b*x[k],y[k])) get[i][j]|=1<<(k-1);
            }
        memset(f,127,sizeof(f));f[0]=0;
        for(int i=0;i<=(1<<n)-1;i++)
            for(int j=1;j<=n;j++)
                if(!((1<<j-1)&i)){
                    for(int k=j+1;k<=n;k++)
                        f[i|get[j][k]]=min(f[i]+1,f[i|get[j][k]]);
                    f[i|1<<(j-1)]=min(f[i]+1,f[i|1<<(j-1)]);
                }
        printf("%d\n",f[(1<<n)-1]);
    }
}

Algorithm Dp