邵阳网站seo,成都企业网站建设公司电话,广西网络推广,wordpress 布局调整正题
题目链接:https://www.luogu.com.cn/problem/P2831 题目大意 nnn个点#xff0c;每次可以射掉在函数yax2bxyax^2bxyax2bx上的点#xff08;a,ba,ba,b自定但是要求a0a0a0#xff09;。求最少射击次数。 解题思路
考虑状压#xff0c;我们发现如果一次射掉…正题
题目链接:https://www.luogu.com.cn/problem/P2831 题目大意
nnn个点每次可以射掉在函数yax2bxyax^2bxyax2bx上的点a,ba,ba,b自定但是要求a0a0a0。求最少射击次数。 解题思路
考虑状压我们发现如果一次射掉两个或以上的点那么一定是一条固定的线如果a≥0a\geq 0a≥0的话就没有了。计算coveri,jcover_{i,j}coveri,j表示如果同时射掉iii和jjj会射掉的点集。
这样就是O(T2nn2)O(T2^nn^2)O(T2nn2)的无法胜任本题考虑如何优化。
我们发现对于一个在目前状态中没有射掉的点xxx如果先射掉别的点再射掉他其实是一样的。所有我们固定每次先射掉编号最小的没有射掉的点即可。时间复杂度O(T2nn)O(T2^nn)O(T2nn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includecmath
using namespace std;
const int N20;
const double eps1e-8;
int T,n,m,MS,f[1N],cover[N][N];
double a,b,x[N],y[N];
void solve(double a1,double b1,double c1,double a2,double b2,double c2){b(c1/a1-c2/a2)/(b1/a1-b2/a2);ac1/a1-b1/a1*b;return;
}
int main()
{scanf(%d,T);while(T--){memset(f,0x3f,sizeof(f));scanf(%d%d,n,m);for(int i0;in;i)scanf(%lf%lf,x[i],y[i]);memset(cover,0,sizeof(cover));for(int i0;in;i)for(int j0;jn;j){if(fabs(x[i]-x[j])eps)continue;solve(x[i]*x[i],x[i],y[i],x[j]*x[j],x[j],y[j]);if(a-eps)continue;for(int k0;kn;k)if(fabs(y[k]-(a*x[k]*x[k]b*x[k]))eps)cover[i][j]|(1k);}MS1n;f[0]0;for(int i0;iMS;i){int x;for(x0;xn;x)if(!((ix)1))break;f[i|(1x)]min(f[i|(1x)],f[i]1);for(int j0;jn;j)f[i|cover[x][j]]min(f[i|cover[x][j]],f[i]1);}printf(%d\n,f[MS-1]);}
}
