@
题意
题解
这道题目不是一道SB的状压吗。
我们设\(f[i]\)，表示射击状态是\(i\)，最少用了多少直线。
\(i\)的第\(j\)位为\(1\)表示射击这个位置。
然后对于每个直线跑背包。
时间复杂度：\(O(Tn^22^n)\)
但是其实有更快做法，限制\(i\)只能被包含最低位的\(1\)的直线所更新，那么就是\(n\)条直线，所以就是\(O(Tn2^n)\)
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define N 20
#define NN 300000
using namespace std;
template <class T>
inline T mymax(T x,T y){return x>y?x:y;}
template <class T>
inline T mymin(T x,T y){return x<y?x:y;}
double f[10][10];
bool gsxy()
{
//有两行相同的会被完全消掉
int n=2;
for(int i=1;i<n;i++)
{
double mmax=0;int id=0;
for(int j=i;j<=n;j++)
{
if(fabs(f[j][i])>=mmax)mmax=fabs(f[j][i]),id=j;
}
if(mmax<=1e-6)return 0;
if(id!=i)swap(f[id],f[i]);
for(int j=i+1;j<=n;j++)
{
double ss=f[j][i]/f[i][i];
for(int k=n+1;k>=i;k--)f[j][k]-=ss*f[i][k];
}
}
for(int i=n;i>=1;i--)
{
if(f[i][i]<=1e-6)return 0;
f[0][i]=f[i][n+1]/f[i][i];
for(int j=i-1;j>=1;j--)f[j][n+1]-=f[j][i]*f[0][i];
}
return 1;
}//高斯消元
//那么解析式就是f[0][1]x^2+f[0][2]x+f[0][3]
struct node
{
double x,y;
}a[N];
int dp[NN],ff[NN];//dp[x]表示的是覆盖x的最少直线数目
int n,m;
int main()
{
int fuck=(1<<18)-1;
for(int i=2;i<=fuck;i++)ff[i]=ff[i>>1]+1;
int T;scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);/*为了防止全部都在一条直线的情况*/
int limit=(1<<n)-1;/*修BUG*/
for(int i=1;i<=limit;i++)dp[i]=dp[i^(i&-i)]+1;
for(int i=1;i<=n;i++)//和(0,0)
{
for(int j=i+1;j<=n;j++)
{
if(dp[(1<<(i-1))+(1<<(j-1))]!=1)
{
f[1][1]=a[i].x*a[i].x;f[1][2]=a[i].x;f[1][3]=a[i].y;
f[2][1]=a[j].x*a[j].x;f[2][2]=a[j].x;f[2][3]=a[j].y;
if(!gsxy())continue;
if(f[0][1]<=-1e-6)//因为必须a<0
{
int x=(1<<(i-1))+(1<<(j-1));
for(int o=j+1;o<=n;o++)
{
if(fabs(f[0][1]*a[o].x*a[o].x+f[0][2]*a[o].x-a[o].y)<=1e-6)x+=(1<<(o-1));//表示这条直线可以覆盖更多的人
}
for(int o=x;o;o=(o-1)&x)dp[o]=1;
int k=limit^x;
for(int o=k;o;o=(o-1)&k)
{
for(int l=(x-1)&x;l;l=(l-1)&x)
{
int p=o^l;
dp[o^x]=mymin(dp[o^x],dp[p]+dp[x]);
}
dp[o^x]=mymin(dp[o^x],dp[o]+dp[x]);
}
}
}
}
}
printf("%d\n",dp[limit]);
}
return 0;
}