题解 P2831 【愤怒的小鸟】

2018-12-25 18:03:31


,第一篇题解,有不妥之处请见谅 思路:

解法:状压DP.

g[x]表示二进制编码为x的状态所用的最小步数。 sol[i]表示第i组解。解共有s组。

二进制编码:

状压DP基本概念,二进制数每一位的1表示可以达到这个点,0表示不能达到这个点。

比如,g[10101001](二进制)表示达到第1,4,6,8个点(十进制)所用的最少抛物线数。

解: 能通过仅1条抛物线所达到的所有的点组成的二进制编码,叫做一个解。 本题主要分为以下几步:

预处理。此处可用递归。首先枚举两个点,通过两个点共抛物线构造二元一次方程,用公式将其解出。

公式:$a_1x+b_1y=c_1,a_2x+b_2y=c_2$,解得$x = \frac{(b2c1-b1c2)}{(a1b2-a2b1)}, y = \frac{(a1c2-a2c1)}{(a1b2-a2b1)}$.

DP。此处可以理解为01背包。背包容量为(1<<n)-1,共s个物品,费用分别为sol[1],sol[2],...,sol[s],价值均为1,且要求把背包装满,求最小价值。 但是有一个极大的漏洞:比如我们要配出(以下均为二进制)10011000这个数,一种正确的配法是10000000+00011000,但是另一种拼法是10000000+00010111+00000001,发生了进位,虽然和依然是10011000,但是第1个点显然被打了$2$次。

改进方法:另加一重循环,判断是否有重复。时间复杂度$O(n)$

本步总时间复杂度:$O(smn)$,其中$m=2^n$,可以证明$s\le \frac{n^2}{2}$,故复杂度$O(2^n*n^3)$,期望得分75~85分。 优化 不难发现,比如一条抛物线恰好打中了1,4,6,8(均为十进制)这四个点,且不能打中其他的点。则这条抛物线使s的值增加了15(即(1),(4),(6),(8),(1,4),(1,6),(1,8),(4,6),(4,8),(6,8),(1,4,6),(1,4,8),(1,6,8),(4,6,8),(1,4,6,8).事实上,由于我们是用最少的抛物线打最多的点,因此最后一种(1,4,6,8)的方案比前14种的任意一种都更优。因此,只需在无法继续递归(即没有其他点可以打)时将方案添加到sol[s]中,很大程度上降低了s的大小。(但并不能改变最坏复杂度,因为有可能特造一数据使得无任意三点共抛物线)

最重要的优化:我们在背包中进行位运算判断是否重复,因此添加了重复的情况还要舍去,多一维复杂度。不妨逆向思考:g[j]=min(g[j],g[j-sol[i]+1),原来可以用要更新的点j的编号来表示用来更新此点的点j-sol[i],现在可以用用来更新此点的点的编号来表示此点。即用g[j]来更新其他点,而不是用其他点来更新g[j].这样,我们就可以写出被更新的点的编号:g[i|sol[j]]. 注意:二进制原来1+1=10,现在1|1=1,不会发生进位,因此无需特判,减小一维复杂度。 总复杂度:$O(s*2^n)$,$s\len^2$,即$O(2^n*n^2)$,期望得分100分。

#include<cstdio>
#include<cstring>
#include<cmath> 
using namespace std;

const int MAXN = 18;
const int MAXM = 262144;
struct Point
{
    double x,y;
};
Point nd[MAXN+2];
int sol[MAXN*MAXN+MAXN];
int g[MAXM+2];
int n,m,c,s;

void solve(double a1,double b1,double c1,double a2,double b2,double c2,double *ansx,double *ansy)
{
    if(a1*b2 != a2*b1)
    {
        *ansx = (b2*c1-b1*c2)/(a1*b2-a2*b1);
        *ansy = (a1*c2-a2*c1)/(a1*b2-a2*b1);
    }
}

void DFS(int pos,int cod,double a,double b)
{
    int i,j;
    double arga,argb;

    if(pos == n) return;
    if(cod == 0)
    {
        for(i=0; i<n; i++)
        {
            for(j=i+1; j<n; j++)
            {
                if(nd[i].x != nd[j].x)
                {
                    solve(nd[i].x*nd[i].x,nd[i].x,nd[i].y,nd[j].x*nd[j].x,nd[j].x,nd[j].y,&arga,&argb);
                    if(arga < -1e-6)
                    {
                        DFS(j,(1<<i)+(1<<j),arga,argb);
                    }
                }
            }
        }
    }
    else
    {
        for(i=pos+1; i<n; i++)
        {
            if(fabs(nd[i].x*nd[i].x*a+nd[i].x*b-nd[i].y) < 1e-12)
            {
                DFS(i,cod+(1<<i),a,b);
                return;
            }
        }
        sol[s] = cod;
        g[cod] = 1;
        s++;
    }
}

bool match(int spos,int gpos)
{
    int i;
    for(i=n-1; i>=0; i--)
    {
        if((sol[spos]&(1<<i)) && (gpos&(1<<i))) return false;
    }
    return true;
}

int main()
{
    int t,i,j;

    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&c);
        m = 1<<n;
        for(i=0; i<n; i++)
        {
            scanf("%lf%lf",&nd[i].x,&nd[i].y);
        }

        if(n == 1)
        {
            printf("1\n");
            continue;
        }
        memset(g,42,sizeof(g));
        memset(sol,0,sizeof(sol));
        s = 0;
        for(i=0; i<n; i++)
        {
            sol[s++] = 1<<i;
            g[1<<i] = 1;
        }
        DFS(0,0,0.0,0.0);

        g[0] = 0;
        for(j=0; j<s; j++)
        {
            for(i=0; i<m; i++)
            {
                if(g[i|sol[j]] > g[i]+1) g[i|sol[j]] = g[i]+1;
            }
        }

        printf("%d\n",g[m-1]);
    }

    return 0;
}