题目大意:
平面直角坐标系的第一象限有n(n<=18)个点,你可以每次给出一个形如y=ax^2+bx的函数把经过这条函数的点消掉,问消掉所有的点至少要多少函数?思路:
枚举每两个点对,可以唯一确定一条函数,再枚举第三个点,判断一下是否会经过这条函数。 状态压缩一下记录每条函数能消掉那些点。 然后就是一个简单的状压DP。 一开始由于把fabs打成了abs,样例都过不去,调了半个下午。 洛谷上随便A,UOJ上被Extra数据hack掉了,把eps从1e-7改成1e-10就A了。1 #include2 #include 3 #include 4 #include 5 inline int getint() { 6 register char ch; 7 while(!isdigit(ch=getchar())); 8 register int x=ch^'0'; 9 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');10 return x;11 }12 const int N=18;13 const double eps=1e-10;14 struct Point {15 double x,y;16 };17 Point p[N];18 int sit[N*N],s;19 int f[1< -eps) continue;39 sit[s]=(1< <