60分做法:
暴力枚举两个没被覆盖点，形成一个合法的抛物线，在扫一遍能在抛物线上的点，打上标记即可。
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
int t;
int n,m,U,w;
double x[30],y[30];
int p[30];
int ans=0;
bool vis[30];
bool check(int id,double a,double b)
{
if(fabs(a*x[id]*x[id]+b*x[id]-y[id])<=0.000001)
return 1;
return 0;
}
void dfs(int cnt,int sum)
{
if(sum>ans||w>U) return;
if(cnt==n)
{
ans=min(ans,sum);
return;
}
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
for(int j=i+1;j<=n;j++)
{
w++;
if(vis[j]) continue;
double a=(x[j]*y[i]-x[i]*y[j])/(x[i]*x[j]*(x[i]-x[j]));
double b=(y[i]-a*x[i]*x[i])/x[i];
if(a>=0) continue;
vis[i]=vis[j]=1;
int tot=0;
for(int k=j+1;k<=n;k++)//因为在前面能选的点，之前也可以枚举到，这种情况可以覆盖到现在这个情况，所以可以从j往后枚举，减少重复情况
{
if(vis[k]) continue;
if(check(k,a,b))
vis[k]=1,p[++tot]=k;
}
dfs(cnt+2+tot,sum+1);
for(int k=1;k<=tot;k++)
vis[p[k]]=0;
vis[i]=vis[j]=0;
}
}
ans=min(n-cnt+sum,ans);
}
int main()
{
scanf("%d",&t); U=20000000/t;//卡时能过75
while(t--)
{
w=0;
ans=1e9;
memset(vis,0,sizeof(vis));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lf%lf",&x[i],&y[i]);
dfs(0,0);
printf("%d
",ans);
}
return 0;
}
满分做法:
看到n<=18,可以想到状压DP。(dp[S])表示表示已经死了的猪的集合状态为S时最少要发射的鸟数（即抛物线）。
考虑转移：
(dp[0]=0)
(dp[S|line[i][j]]=min(dp[S|line[i][j]],dp[S]+1))
(dp[S|(1<<(i-1)]=min(dp[S|(1<<(i-1)],dp[S]+1))（单独打一个猪）
(line[i][j])表示第i个点和第j个点连成的抛物线可以打死猪的集合。
本题可以优化到(O(Tn2^n)).令(low[S])表示S状态第一个零的位置。这个位置是一定要打的，如果这一次转移不打，那以后还要再回过头来打，这就是多余的转移。所以由 S扩展的转移的所有线都要经过(low[S])。之后枚举抛物线即可。
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
const int maxm=1<<20;
const double eq=1e-8;
int t;
int n,m;
double x[30],y[30];
int low[maxm];//表示i状态的第一个0的位置
int dp[maxm];//表示i状态的最少抛物线数
int line[30][30];//表示经过i,j的抛物细经过所有点的状态
bool check(int id,double a,double b)
{
if(fabs(a*x[id]*x[id]+b*x[id]-y[id])<=eq)
return 1;
return 0;
}
int main()
{
for(int i=0;i<(1<<18);i++)
{
int j=1;
for(;j<=18,i&(1<<(j-1));j++);
low[i]=j;
}
scanf("%d",&t);
while(t--)
{
memset(dp,63,sizeof(dp));
memset(line,0,sizeof(line));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lf%lf",&x[i],&y[i]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(fabs(x[i]-x[j])<eq) continue;
double a=(x[j]*y[i]-x[i]*y[j])/(x[i]*x[j]*(x[i]-x[j]));
double b=(y[i]-a*x[i]*x[i])/x[i];
if(a>-eq) continue;
for(int k=1;k<=n;k++)
{
if(check(k,a,b))
line[i][j]|=(1<<(k-1));
}
}
}
dp[0]=0;
for(int i=0;i<(1<<n);i++)
{
int j=low[i];//能过的点尽量早过
dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]+1);
for(int k=1;k<=n;k++)
dp[i|line[j][k]]=min(dp[i|line[j][k]],dp[i]+1);
}
printf("%d
",dp[(1<<n)-1]);
}
return 0;
}