题目内容
P2831
大意：(0,0) 处有一弹弓，有 n 只猪猪，弹弓发出的炮弹路径为 y=ax^2+bx，其中 a > 0，求最少的抛物线数量打掉所有猪猪。
解题思路
一开始的暴搜调了我很久，但是最后都只有 60 分，具体的思路就是两只两只的枚举猪猪，如果发现两只可以构成合法抛物线，那么就清算抛物线上的其他猪猪然后继续暴搜，但是复杂度比较高。状态的存储使用状压。
#include <cstdio>
#include <cmath>
#include <bitset>
#include <cstring>
#include <iostream>
#define EPS 1e-6
using namespace std;
class P2831
{
private:
struct point
{
double x,y;
};
int ans;
int n,m;
point pig[19];
int vis[1<<18];
inline bool ison(point p,double a,double b)//判断点在不在抛物线上
{
return fabs(a*p.x*p.x+b*p.x-p.y)<=EPS;
}
inline bool calc(point d1,point d2,double &a,double &b)//计算过(x1,y1)和(x2,y2)的抛物线表达式
{
if(fabs(d1.x-d2.x)<EPS)
{
//cout<<"debug1"<<endl;
return false;
}
if(fabs(d2.y/d2.x-d1.y/d1.x)<EPS)
{
//cout<<"debug2"<<endl;
return false;
}
b=(d1.y*d2.x*d2.x/d1.x/d1.x-d2.y)/((d2.x*d2.x/d1.x)-d2.x);
a=(d1.y-b*d1.x)/d1.x/d1.x;
//cout<<"a:"<<a<<" b:"<<b<<endl;
if(a>0)
return false;
return true;
}
void dfs(int cur,int opt,int step)
{
vis[cur]=min(vis[cur],step);
//cout<<"step:"<<step<<' '<<cur<<endl;
if(cur==(1<<n)-1)
{
ans=min(ans,step);
return;
}
if(opt==1 && step>n/3.0+1)
return;
if(step>=ans || step>vis[cur])
return;
for(int i=0;i<n;i++)
{
bool flag=0;
int now=cur;
if(now&(1<<i))
continue;
now|=(1<<i);
for(int j=0;j<n;j++)
{
int now2=now;
if(now2&(1<<j))
continue;
double a,b;
if(!calc(pig[i],pig[j],a,b))
continue;
flag=1;
now2|=(1<<j);
for(int k=0;k<n;k++)
if((!now2&(1<<k)) && ison(pig[k],a,b))
now2|=(1<<k);
dfs(now2,opt,step+1);
}
if(!flag)
dfs(now,opt,step+1);
}
}
public:
int solve()
{
ans=0x3f3f3f3f;
memset(vis,0x3f,sizeof(vis));
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
scanf("%lf %lf",&pig[i].x,&pig[i].y);
dfs(0,m,0);
return ans;
}
};
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
P2831 a;
printf("%d\n",a.solve());
}
return 0;
}
于是我放弃了调暴搜，在题解区发现了一种神奇的东西叫状压 dp，用 f_i 表示状态 i 需要的最少抛物线条数。同时抛物线预处理成能通过的点的集合，记作 para_j，转移方程如下：
f_{i|para_j}=\min(f_{i|para_j},f_i+1)
预处理抛物线的时候首先枚举单个的猪猪，因为每只猪猪必过一个抛物线，然后再枚举第二个猪猪，如果能构成的抛物线合法的话再将其他在抛物线上的点加入即可。
关于数学：要求过 (x_1,y_1) 和 (x_2,y_2) 的抛物线 y=ax^2+bx 中 a 和 b 的值，列出来式子然后消元即可。
b=\frac{\frac{y_1x^2_2}{x_1^2}-y_2}{\frac{x_2^2}{x_1}-x_2}\
a=\frac{y_1-bx_1}{x_1^2}
代码如下：
#include <cstdio>
#include <cmath>
#include <cstring>
#define EPS 1e-6
using namespace std;
struct point
{
double x,y;
};
int n,m,para[200],f[1<<18],cnt;
inline bool ison(point p,double a,double b)//判断点在不在抛物线上
{
return fabs(a*p.x*p.x+b*p.x-p.y)<=EPS;
}
inline bool calc(point d1,point d2,double &a,double &b)//计算过(x1,y1)和(x2,y2)的抛物线表达式
{
if(fabs(d1.x-d2.x)<EPS)//判断横坐标相等的情况
return false;
if(fabs(d2.y/d2.x-d1.y/d1.x)<EPS)//判断构不成抛物线的情况
return false;
b=(d1.y*d2.x*d2.x/d1.x/d1.x-d2.y)/((d2.x*d2.x/d1.x)-d2.x);
a=(d1.y-b*d1.x)/d1.x/d1.x;
if(a>0)
return false;
return true;
}
inline int min(int a,int b)
{
return a<b?a:b;
}
void pre()//预处理
{
scanf("%d %d",&n,&m);
memset(f,0x3f,sizeof(f));//先赋极大值
cnt=0;//cnt为抛物线的数量
point pig[18];
for(int i=0;i<n;i++)
scanf("%lf %lf",&pig[i].x,&pig[i].y);
for(int i=0;i<n;i++)
{
para[cnt++]=1<<i;//先加入一个新抛物线
for(int j=i+1,vis=0;j<n;j++)//定义的vis是枚举过的小猪，避免重复
{
if((1<<j)&vis)//判重
continue;
double a,b;
if(!calc(pig[i],pig[j],a,b))//如果不合法
continue;
para[cnt]=1<<i;//先暂时加进去只有第一只猪猪的抛物线
for(int k=j;k<n;k++)//然后枚举加新点进去
{
if(ison(pig[k],a,b))//如果第k只猪猪在上面
{
vis|=(1<<k);//更新vis数组
para[cnt]|=(1<<k);//更新抛物线
}
}
cnt++;//然后抛物线的条数要加一
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
pre();
f[0]=0;
for(int i=0;i<(1<<n);i++)//枚举每个状态
for(int j=0;j<cnt;j++)//枚举每一条抛物线
f[i|para[j]]=min(f[i|para[j]],f[i]+1);//状态转移
printf("%d\n",f[(1<<n)-1]);//输出答案
}
return 0;
}
