摘要：
60分算法：1.如果使用暴力，我们会删除一些线段并进入下一个状态。一种状态是指当前平面中还剩多少点；2.注意：无论您如何从当前状态删除点，从上一状态到当前状态的决策都不会受到影响。：）21使用namespacestd；22constdoubleex=1e-8；23intst[20]＝{1}；2425英寸，m；26doublex[20]，y[20]；27intc[20][20]；28intf[+5]；2930voidwork（）｛31scanf；32,33 scanf；34memset；35,36用于｛37 doublea＝/；38 if continue；39 doubleb＝/x1；40用于41 if 42 c[i][j]+=st[k]；43｝44memset；45f[0]=0；46intlim=-1；47intINF=f[1]；48代表49如果（f[i]！=INF）50代表51如果（！）｛52 f[i|st[j]]=最小值；对于｛54 inttmp=i|c[j][k]为53；55 f[tmp]=最小；56｝57｝58 printf；59｝6061itmin（）｛62for63st[i]=st[i-1]˂˂1；64intt；65scanf；66while（t--）67 work（）；68return0；69｝
Description
Input
![[NOIp 2016]愤怒的小鸟第2张](https://images2017.cnblogs.com/blog/1207671/201709/1207671-20170904205428522-1356237790.png)
![[NOIp 2016]愤怒的小鸟第3张](https://images2017.cnblogs.com/blog/1207671/201709/1207671-20170904205556663-1872927655.png)
Output
![[NOIp 2016]愤怒的小鸟第4张](https://images2017.cnblogs.com/blog/1207671/201709/1207671-20170904205623210-1924115519.png)
Sample Input
2
2 0
1.00 3.00
3.00 3.00
5 2
1.00 5.00
2.00 8.00
3.00 9.00
4.00 8.00
5.00 5.00
Sample Output
1
1
Sample Explanation
![[NOIp 2016]愤怒的小鸟第5张](https://images2017.cnblogs.com/blog/1207671/201709/1207671-20170904205916147-1050368132.png)
HINT
题解
暴力做法:
1、因为三点可以确定一条抛物线,又必过原点,那么只需要再找两个点就能确定一条抛物线;
2、枚举点对,求出抛物线方程,注意两点的$x$坐标不能相等,抛物线的二次项系数必须小于$0$;
3、删掉在抛物线上的点,进入下一层继续枚举。
60分算法:
1、如果使用暴力,我们会删掉一些线段进入下一个状态,一个状态是指现在平面内还剩多少个点;
2、注意到一点:从当前状态无论以什么方式删点,均不会影响之前状态到当前状态的决策。也就是说:在之前的状态时,我们只需要考虑,怎样删点来到达当前状态即可,而不用管当前状态下如何删点来到达下一个状态;
3、这具备明显的无后效性,我们用一个二进制数$S$来表示一个状态,若$S$的第$i$位为$1$,则表示第$(i+1)$个点还存在于平面内,那么状态压缩的$DP$可以解决;
4、同样对于每个状态枚举抛物线即可。
100分算法:
1、平面内有$n$个点,共$2^n$个状态,每次枚举抛物线还要检查每个点,需要$O(n^3)$复杂度;
2、每次都要枚举抛物线经过的两个点,即抛物线必定会删去的两个点。既然我们的最终目标是将当前状态所有的点都删去,那么可以知道,删掉所有点的最优方案中,一定会有一条抛物线经过当前状态的第一个点(否则就没法删掉它了);
3、那么我们只需要枚举经过当前状态第一个点的抛物线就可以(这么做一定不会有错误的决策)。
1 #include <set> 2 #include <map> 3 #include <ctime> 4 #include <cmath> 5 #include <queue> 6 #include <stack> 7 #include <vector> 8 #include <cstdio> 9 #include <string> 10 #include <cstring> 11 #include <cstdlib> 12 #include <iostream> 13 #include <algorithm> 14 #define x1 x[i] 15 #define x2 x[j] 16 #define y1 y[i] 17 #define y2 y[j] 18 #define LL long long 19 #define Max(a, b) ((a) > (b) ? (a) : (b)) 20 #define Min(a, b) ((a) < (b) ? (a) : (b)) 21 using namespace std; 22 const double ex=1e-8; 23 int st[20] = {1}; 24 25 int n, m; 26 double x[20], y[20]; 27 int c[20][20]; 28 int f[(1<<18)+5]; 29 30 void work(){ 31 scanf("%d%d", &n, &m); 32 for (int i = 0; i < n; i++) 33 scanf("%lf%lf", &x[i], &y[i]); 34 memset(c, 0, sizeof(c)); 35 for (int i = 0; i < n; i++) 36 for (int j = i+1; j < n; j++){ 37 double a = (x1*y2-y1*x2)/(x1*x2*x2-x1*x1*x2); 38 if (a >= 0) continue; 39 double b = (y1-a*x1*x1)/x1; 40 for (int k = 0; k < n; k++) 41 if (abs(y[k]-a*x[k]*x[k]-b*x[k]) <= ex) 42 c[i][j]+=st[k]; 43 } 44 memset(f, 127, sizeof(f)); 45 f[0]=0; 46 int lim = (1<<n)-1; 47 int INF = f[1]; 48 for (int i = 0; i <= lim; i++) 49 if (f[i] != INF) 50 for (int j = 0; j < n; j++) 51 if (!(i&st[j])){ 52 f[i|st[j]] = Min(f[i|st[j]], f[i]+1); 53 for (int k = j+1; k < n; k++){ 54 int tmp = i|c[j][k]; 55 f[tmp] = Min(f[tmp], f[i]+1); 56 } 57 } 58 printf("%d ", f[lim]); 59 } 60 61 int main(){ 62 for (int i = 1; i <= 18; i++) 63 st[i] = st[i-1]<<1; 64 int t; 65 scanf("%d", &t); 66 while (t--) 67 work(); 68 return 0; 69 }