题目：https://www.luogu.org/problemnew/show/P2831
一开始想 n^3 贪心来着；
先按 x 排个序，那么第一个不就一定要打了么？
在枚举后面某一个，和它形成一条抛物线，选能顺便打掉最多的那个；
然后连样例都过不了...
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define eps 1e-9
using namespace std;
int T,n,m,ans;
bool vis[];
struct N{
double x,y;
}p[];
bool cmp(N x,N y){return x.x<y.x;}
int main()
{
scanf("%d",&T);
while(T--)
{
memset(vis,,sizeof vis);
ans=;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
sort(p+,p+n+,cmp);
for(int i=;i<=n;i++)
{
if(vis[i])continue; vis[i]=;
// printf("i=%d\n",i);
double x1=p[i].x, y1=p[i].y, xx=x1*x1, x2,y2,xy,a,b,aa=,bb=;
for(int j=i+;j<=n;j++)
{
int cnt=,mx=;
if(vis[j]||p[j].x==p[i].x)continue;
x2=p[j].x; y2=p[j].y; xy=x2*x2;
// y2=y2/x2*x1; xy=xy/x2*x1;
// a=(y1-y2)/(xx-xy);
a=(y1*x2-y2*x1)/(x1*x2*(x1-x2));
b=(y1-a*xx)/x1;
// printf("%lf %lf\n",a,b);
for(int k=j+;k<=n;k++)
{
if(vis[k])continue;
double tx=p[k].x,ty=p[k].y;
if(a*tx*tx+b*tx-ty<eps)cnt++;
}
if(cnt>mx)mx=cnt,aa=a,bb=b;
}
if(aa||bb)
for(int j=i+;j<=n;j++)
if(fabs(aa*p[j].x*p[j].x+bb*p[j].x-p[j].y)<eps)vis[j]=;
ans++;
}
printf("%d\n",ans);
}
return ;
}
囧
仔细想想，贪心可能是错的；
正解是状压DP，DP真是与贪心相对的正确解法啊...
n 很小，所以想到状压，记录所有可能的抛物线的打猪情况；
然后类似背包转移即可...
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define eps 1e-8
using namespace std;
int T,n,m,f[],g[],tot;
double x[],y[];
bool ck(int k,double a,double b)
{
return fabs(a*x[k]*x[k]+b*x[k]-y[k])<eps;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
memset(g,,sizeof g); double a,b;
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
{
if(x[i]==x[j])continue;
a=(y[i]*x[j]-y[j]*x[i])/(x[i]*x[j]*(x[i]-x[j]));
b=(y[i]-a*x[i]*x[i])/x[i];
if(a>=)continue;//>=而非> !
tot++;
for(int k=;k<=n;k++)
if(ck(k,a,b))g[tot]|=(<<(k-));
}
for(int i=;i<n;i++)g[++tot]|=(<<i);
sort(g+,g+tot+);
tot=unique(g+,g+tot+)-g-;
memset(f,0x3f,sizeof f); f[]=;
for(int i=;i<(<<n);i++)
for(int j=;j<=tot;j++)
f[i|g[j]]=min(f[i|g[j]],f[i]+);
printf("%d\n",f[(<<n)-]);
}
return ;
}