09
2019
08

2016NOIP提高组-愤怒的小鸟

题目链接:http://ybt.ssoier.cn:8088/problem_show.php?pid=1898


1)n<=18考虑状态压缩,把n个小猪能否被消灭用二进制的1,0来表示

比如状态S=15 二进制是  000000000000001111  表示状态S下第1,2,3,4 只小猪可以被消灭

dp[s]就表示状态S下消灭这些小猪最少需要的抛物线条数。

2)因此我们枚举任意两只小猪构成的抛物线,用st[i][j] 表示i和j两只小猪构成的抛物线能够消灭小猪的状态

比如st[i][j]=15 二进制  000000000000001111        就是说i,j构成的抛物线  可以消灭1,2,3,4 这四只小猪。

3)然后我们开始转移dp,从 1到 2^n-1枚举每一种状态,然后看此状态下,单个的小猪(即某个二进制位置上为0)  j,k能不能两两组合,如果能组合,可以考虑组合,则dp[i|st[j][k]]=min(dp[i|st[j][k]],dp[i]+1) 也可以考虑自己单独被消灭可能更优,则 

dp[i|1<<(j-1)]=min(dp[i|1<<(j-1)],dp[i]+1)

有的单只小猪只能自己被消灭,则价格特判,同样  dp[i|1<<(j-1)]=min(dp[i|1<<(j-1)],dp[i]+1)

#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
typedef double dd;

int read()
{
    int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

const int maxn=300010;
int t,n,m;
struct node{dd x,y;}pi[20];
int st[20][20],judge[20];
int dp[maxn];

int calc(int d1,int d2)
{
    dd x1=pi[d1].x,y1=pi[d1].y;
    dd x2=pi[d2].x,y2=pi[d2].y;
    if(x1==x2) return 0;

    dd tx=x1*x1*x2-x2*x2*x1,ty=y1*x2-y2*x1;
    dd a=ty/tx,b=(y1-a*x1*x1)/x1;
    if(a>=0) return 0;//这两只小猪不能被一起消灭

    int res=0;//记录这条抛物线能消灭的小猪
    judge[d1]=judge[d2]=1;
    //枚举能消灭的小猪 
    for(int i=1;i<=n;++i)
    {
        dd x=pi[i].x,y=pi[i].y;
        if(fabs(a*x*x+b*x-y)<1e-7) 
        //res对应的位置为1,表示可以消灭第i只小猪
        res|=1<<(i-1),dp[1<<(i-1)]=dp[res]=1;
    }
    return res;
}

int main()
{
    t=read();
    while(t--)
    {
        memset(dp,67,sizeof(dp));
        memset(judge,0,sizeof(judge));
        n=read();m=read();
        for(int i=1;i<=n;++i)
        {
            scanf("%lf%lf",&pi[i].x,&pi[i].y);
            dp[1<<(i-1)]=1;//初始化只射一只小鸟 
        }

        for(int i=1;i<=n;++i)
        for(int j=1;j<i;++j)
        st[i][j]=calc(i,j);//每两只小猪一起消灭的抛物线

        for(int i=1;i<=(1<<n)-1;++i)//枚举每个状态
        {
            for(int j=1;j<=n;++j)//枚举下一个没被消灭的小猪
            {
            	//可以消灭 
                if( ((i>>(j-1))&1)== 1 )continue;
                //j只能单独被消灭 
                if(!judge[j]){dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]+1);continue;}
                //j和另一只小猪组成抛物线,更新i|st[j][k] 
                for(int k=1;k<j;++k)//枚举另一个小猪一起组成抛物线
                {
                	//可以消灭 
                    if( (i&(1<<(k-1))) == 1 )continue;
                    //j和k构成抛物线dp[i]+1,更新i|st[j][k] 
                    dp[i|st[j][k]]=min(dp[i|st[j][k]],dp[i]+1);
                }
                //单独消灭j可能更优
                dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]+1);
                
            }
        }
        printf("%d\n",dp[(1<<n)-1]);
    }
    return 0;
}



此题还有一个思路就是搜索,关键是dfs参数的设定要好好理解,代码如下:

/*思路:搜索。
对于第i只猪,如果它已经被前面所构造的某条抛物线经过了,
就不用处理了,继续往下搜索。否则,就有两种选择,第一种
是与前面某一只单独的猪(即这只猪未与其它猪组成抛物线)
组成抛物线,因为两只猪最多也只能被一条抛物线相连;第二
种是暂时不与其它单独的猪组成抛物线。最后,将抛物线的条
数与余下的猪的个数相加(因为单独的一只猪也要一条抛物线
将其击中)就是搜索出来的一个合法的结果。*/ 
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<string>
#include<sstream>
#include<cstring>
#include<cmath>
    using namespace std;
    const double eps=1e-8;
/*因为浮点数的精度计算太过复杂,像3.14这样的数存在浮
点型变量里存的可能是3.139999999,也有可能是3.140000001,
所以不能直接用“==”判断两个浮点数是否相等。在这种情况
下,就允许判断两个浮点数为相等时,两数之间存在微小的误差,
这个“微小的误差”要取一个较小的数,比如1e-8,这样就不
会判不出也不会误判了。*/
bool dy(double a,double b)//判断两个浮点数是否相等的函数 
{
    //如果a和b之间相差的值小于eps(即1e-8),就说明它们是相等的 
    return fabs(a-b)<eps;//fabs用于取浮点数的绝对值 
}
    int n=0,m=0,ans=0;
    //x数组存每只猪的x坐标,y数组存每只猪的y坐标
    //pwxa数组存每条已构造的抛物线的参数a,pwxb数组存每条已构造的抛物线的参数b
    //tx数组存每只单独的猪的x坐标,ty数组存每只单独的猪的y坐标 
    double x[20],y[20],pwxa[20],pwxb[20],tx[20],ty[20];
//dfs(c,u,v)表示当前搜到第c只猪,已构造抛物线的数量为u,单独的猪的数量为v时的情况 
//注意:当前抛物线的总数量为(u+v)条,因为除已有的抛物线外,每一只单独的猪也需要一条抛物线来击中它 
void dfs(int c,int u,int v)
{
    //最优性剪枝,因为即使后面的每一只猪都被当前已构造的抛物线击中, 
    //或者与其它单独的猪组成抛物线,抛物线的总数量还是(u+v),不会减少,
    //所以如果抛物线的总数量已经大于等于当前的最优解时,搜下去也不会
    //比当前更优了,就不用继续搜下去了。
    if(u+v>=ans) return;
    if(c>n)//如果搜完了 
    {
        ans=u+v;//记录答案,因为前面已经有最优性剪枝了,所以没被剪掉的答案一定比当前更优 
        return;//结束 
    }
    bool flag=false;//记录是否被已构造的抛物线经过 
    for(int i=1;i<=u;i++)//枚举已构造的抛物线 
        //将这一条抛物线的参数与当前猪的x坐标带进函数解析式算一遍,
        //如果结果等于当前猪的y坐标,就说明当前猪已经被已构造的抛物线经过了 
        if(dy(pwxa[i]*x[c]*x[c]+pwxb[i]*x[c],y[c]))
        {
            dfs(c+1,u,v);//被经过了就直接往下搜 
            flag=true;//记录 
            break;//退出循环,既然当前猪已经被经过了,再继续判断也没有意义了
        }
    if(!flag)//如果没有被经过 
    {
        for(int i=1;i<=v;i++)//枚举单独的猪 
        {
            //如果当前猪与这一只单独的猪的x坐标相同,就说明它们不能组成一条
            //抛物线。因为若想使它们组成一条抛物线,弹弓的位置就必须是它们的正下
            //方,然后往上垂直发射,但是弹弓的位置固定在(0,0),而猪的x坐标又大于
            //0(题目数据范围),所以它们不能组成一条抛物线。如果不加这个判
            //断的话就会计算出一些奇奇怪怪的东西,影响后面的判断,所以还是加上为好。 
            if(dy(x[c],tx[i])) continue;//如果当前猪与这一只单独的猪的x坐标相同,跳过这一次循环
            //求参数a、b的过程实际上就是解一个二元一次方程组,比如说有两只猪的坐标分别是(1,3)和(3,3), 
            //现在要求出它们所组成的抛物线的参数a与参数b。将两只猪的坐标分别代入到函数解析式中,
            //就可以得出一个方程组: 3=a+b  3=9a+3b 。这是,我们可以用加减消元法消掉b,将两个方程
            //分别乘上另一个方程的b的系数,得:9=3a+3b 3=9a+3b。这样,两个方程中的b的系数就一致了,
            //然后直接用一个式子减去另一个式子,再将a的系数化为一即可。最后再将a带入到回任意一个方程求b即可。
            //因为这里的所有方程都长一个样,所以这一种方法是通用的。 
            double a=(y[c]*tx[i]-ty[i]*x[c])/(x[c]*x[c]*tx[i]-tx[i]*tx[i]*x[c]);//求参数a 
            double b=(y[c]-x[c]*x[c]*a)/x[c];//将a代入求参数b 
            if(a<0)//如果这一个解是合法的,就说明当前猪与这一只单独的猪可以组成抛物线 
            {   
                pwxa[u+1]=a;//记录抛物线的参数a 
                pwxb[u+1]=b;//记录抛物线的参数b
                //将这一只单独的猪从数组中删去,因为它已经和当前猪组成抛物线,不再单独了 
                double q=tx[i],w=ty[i];
                for(int j=i;j<v;j++)
                {
                    tx[j]=tx[j+1];
                    ty[j]=ty[j+1];
                }
                dfs(c+1,u+1,v-1);//继续往下搜
                //将这一只单独的猪放回数组(回溯) 
                for(int j=v;j>i;j--) 
                {
                    tx[j]=tx[j-1];
                    ty[j]=ty[j-1];
                }
                tx[i]=q;
                ty[i]=w;
            }
        }
        //还有一种选择:暂时不与其它猪组成抛物线 
        tx[v+1]=x[c];
        ty[v+1]=y[c];
        dfs(c+1,u,v+1);//继续往下搜 
    }
}
int main()
{
    int T=0;
    scanf("%d",&T);
    for(int Q=1;Q<=T;Q++)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);
        ans=100;//记得初始化 
        dfs(1,0,0);//搜 
        printf("%d\n",ans); 
    } 
    return 0;//完美地结束 
}

好好理解一下吧。

« 上一篇 下一篇 »

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。