要减肥月饼

文章
4
资源
0
加入时间
2年10月21天

uoj265【2016提高】愤怒的小鸟(状压dp)

首先每两个点可以确定一条抛物线,一条抛物线可能打掉很多猪。所以我们先O(n2)O(n^2)预处理一下第i个点和第j个点所确定的抛物线(算个公式就好了),如果a<0才合法,(注意精度问题,还有特判横坐标相等的,小心除0)然后对于这条抛物线,如果合法的话,我们O(n)O(n)扫一遍,看有没有其他的点也在这条抛物线上。用b数组记录一下(n<=18,我们显然可以用二进制压缩状态,共2n2^n种,把这条抛物线