Loading...

洛谷P2831 愤怒的小鸟

check评论:0 条 remove_red_eye浏览量:63 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-11-08

原题链接

  • 题目描述
给定n个点,求最少构造多少条抛物线使得所有点都被覆盖,其中抛物线解析式必须满足y=ax^2+bx且a<0
  • 题目分析

显然可以先两两枚举点来求出所有的$a$和$b$,一个点的情况单独算

然后算出每条抛物线可以经过哪些点,可以状态压缩来做

$dp[j|pre[k]]=min(dp[j|pre[k]],dp[j]+1)$,其中$pre[k]$代表第$k$条抛物线的状态

然后输出答案就好

  • 代码实现
/* Summer Pockets */
/*deco loves Chino*/
#include <bits/stdc++.h>
using namespace std;
int t,n; 
long double a[20],b[20],xa[410],xb[410];
int dp[1200010],cnt,pre[410];
void gpre()
{
    for(int i=1;i<=cnt;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(fabs(xa[i]*a[j]*a[j]+xb[i]*a[j]-b[j])<1e-6)
            {
                pre[i]|=(1<<(j-1));
            }
        }
    }
}
int main()
{
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        memset(pre,0,sizeof(pre));
        memset(dp,0x3f,sizeof(dp));
        dp[0]=0;
        int x;
        scanf("%d%d",&n,&x);
        for(int j=1;j<=n;j++)
        {
            scanf("%Lf%Lf",&a[j],&b[j]);    
        }    
        cnt=0;
        for(int j=1;j<=n;j++)
        {
            for(int k=j+1;k<=n;k++)
            {
                if(fabs(a[j]-a[k])<1e-6)
                {
                    continue;
                }
                xa[++cnt]=(a[j]*b[k]-a[k]*b[j]);
                xa[cnt]/=(a[j]*a[k]*a[k]-a[j]*a[j]*a[k]);
                xb[cnt]=(a[k]*a[k]*b[j]-a[j]*a[j]*b[k]);
                xb[cnt]/=(a[j]*a[k]*a[k]-a[j]*a[j]*a[k]);
                if((xa[cnt]>-1e-8))
                {
                    cnt--;
                }
            }
        }
        gpre();
        for(int j=1;j<=n;++j)
        {
            pre[++cnt]=(1<<(j-1));
        }
        for(int j=0;j<(1<<n);j++)
        {
            for(int k=1;k<=cnt;k++)
            {
                dp[j|pre[k]]=min(dp[j|pre[k]],dp[j]+1);
            }
        }
        cout<<dp[((1<<n)-1)]<<"\n";
    }
    return 0;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名