NOIP2016D2T3愤怒的小鸟-JDOJ3141


艾玛终于会写这道题了……


NOIP2016D2T3 愤怒的小鸟

题目大意:给你平面直角坐标系内第一象限的n个点,请用形如y=a*x^2+b*x的二次函数将每个点都覆盖到,问最少需要多少条抛物线。

这道题当年各种不会……现在发现其实使用状态压缩DP配上一系列的奇技淫巧然后就搞定啦~

首先进行DFS,找出所有对答案有贡献的抛物线(枚举两个点,三点确定一个二次函数,然后找到所有可能覆盖的点),sol[i]表示第i种可能的抛物线所能覆盖的情况。

然后进行状态压缩DP,f[i]表示攻击小猪状态为i的时候用的最少的抛物线数量。那么我们对于每一个f[s]都找到它的所有子集,如果这个子集是有贡献的那么我们就尝试更新f[s]。最总即可得到正解。

很难调试,不过调试结束就很棒了OvO在这里我使用了结构体存储所有可行方案的同时存储了对应的a,b,调试起来美滋滋啊23333

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
int cnt,t,n,m,pwx[30][30],f[300100];
bool use[300100];
 
struct point{
    double x,y;
}pig[20];
 
struct solution{
    int ans,xa,xb;
}sol[1000100];
 
void calcavail(int tx,int ty)
{
    int tres=0;
    double xa=pig[tx].x,xb=pig[ty].x,ya=pig[tx].y,yb=pig[ty].y;
    if(fabs(xa-xb)<1e-6) return;
    double ta=((ya*xb)-(xa*yb))/((xa*xa*xb)-(xa*xb*xb));
    if(ta>(-1e-6)) return;
    double tb=(ya-(ta*xa*xa))/xa;
    for(int i=1;i<=n;++i){
        if(i==tx||i==ty) continue;
        double tmp=ta*pig[i].x*pig[i].x+tb*pig[i].x;
        if(fabs(tmp-pig[i].y)<1e-6)
            tres+=(1<<(i-1));
    }
    tres+=(1<<(tx-1))+(1<<(ty-1));
    if(!use[tres]){
        use[tres]=true;
        sol[++cnt].ans=tres;
        sol[cnt].xa=ta;
        sol[cnt].xb=tb;
    }
    return;
}
 
int main()
{
    scanf("%d",&t);
    while(t--){
        memset(use,false,sizeof use);
        cnt=0;
        scanf("%d%*d",&n);
        for(int i=1;i<=n;++i) scanf("%lf%lf",&pig[i].x,&pig[i].y);
        for(int i=1;i<=n;++i)
            for(int j=i+1;j<=n;++j)
                calcavail(i,j);
        /*
        for(int i=1;i<=cnt;++i){
            for(int j=0;j<n;++j){
                if((1<<j)&sol[i].ans) printf("x");
                else printf("o");
            }
            printf(" %d %d\n",sol[i].xa,sol[i].xb);
        }
        */
        memset(f,0x3f,sizeof f);
        f[0]=0;
        for(int i=1;i<=n;++i) sol[++cnt].ans=1<<(i-1);
        for(int s=1;s<(1<<n);++s){
            for(int i=1;i<=cnt;++i)
                if(s&sol[i].ans)
                    f[s]=min(f[s],f[s^(s&sol[i].ans)]);
            f[s]++;
        }
        printf("%d\n",f[(1<<n)-1]);
    }
    return 0;
}

 

声明:TonyZhao's Home|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - NOIP2016D2T3愤怒的小鸟-JDOJ3141


不骗了,不骗了。
A Simple OIer fighting tooth and nail.