非常有趣的状压DP。（对反正我自己又没想出来）
因为猪的数目非常的少，还是能想到状压DP。之后，因为首先小鸟都是从原点发射的，所以我们只需要两只猪就可以确定一条抛物线。
既然如此，我们就可以枚举每一对猪，计算出来抛物线的解析式，之后，因为有的时候一条抛物线可以砸死不只一只猪，所以我们可以再枚举一遍，如果猪在这条抛物线上我们就把这条抛物线能消灭的猪叠加。一条抛物线能消灭的猪使用一个压缩状态的二进制数来表示。
在DP的时候，我们考虑所有的情况，对于每种情况去枚举每一只没有被消灭的猪，再枚举另一只猪与之配对。有一些猪只能单独消灭，那就把他们单独计算。还有一些猪在被单独消灭的时候情况可能更优，那我们就多进行一步dp即可。每次在dp的时候更新使用按位或，最后的答案就是dp[(1<<n)-1]。
计算抛物线的式子自己推一下就好。看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(‘\n‘) using namespace std; const int M = 1005; const int N = 1000005; const int INF = 1e9; double eps = 1e-7; typedef long long ll; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘) { if(ch == ‘-‘) op = -1; ch = getchar(); } while(ch >= ‘0‘ && ch <= ‘9‘) { ans *= 10; ans += ch - ‘0‘; ch = getchar(); } return ans * op; } int t,n,m,dp[N],st[25][25]; bool pd[M]; double x[M],y[M]; int calc(int p,int q) { if(x[p] == x[q]) return 0; double a = ((x[q] * y[p] / x[p]) - y[q]) / (x[q] * (x[p] - x[q])); double b = (y[p] - x[p] * x[p] * a) / x[p]; // printf("%.2lf %.2lf\n",a,b); if(a >= 0) return 0; int res = 0; pd[p] = pd[q] = 1;//可以不单独消灭 rep(i,1,n)//寻找其他可以被该小鸟消灭的猪 { double dx = x[i],dy = y[i]; if(fabs(a * dx * dx + b * dx - dy) < eps) res |= 1 << (i-1),dp[res] = 1; } return res; } int main() { t = read(); while(t--) { memset(dp,127/3,sizeof(dp)); memset(pd,0,sizeof(pd)); memset(st,0,sizeof(st)); n = read(),m = read(); rep(i,1,n) scanf("%lf%lf",&x[i],&y[i]),dp[1<<(i-1)] = 1;//消灭当前点的小猪需要一只鸟 rep(i,1,n) rep(j,1,i-1) st[i][j] = calc(i,j);//计算每条抛物线能打到的猪 rep(i,1,(1<<n)-1) { rep(j,1,n) { if(i & (1<<(j-1))) continue;//这猪已经G了 if(!pd[j]) //只能单独消灭 { dp[i|1<<(j-1)] = min(dp[i|1<<(j-1)],dp[i]+1); continue; } rep(k,1,j-1) { if(i & (1<<(k-1))) continue;//这猪G了 dp[i|st[j][k]] = min(dp[i|st[j][k]],dp[i] + 1);//更新答案 } dp[i|1<<(j-1)] = min(dp[i|1<<(j-1)],dp[i] + 1);//单独消灭更好的话在这里更新 } } printf("%d\n",dp[(1<<n)-1]);输出答案 } return 0; } /* 1 2 0 1.00 3.00 3.00 3.00 */
原文：https://www.cnblogs.com/captain1/p/9607366.html