【洛谷】【状压DP】P2831 愤怒的小鸟

洛谷 P2831 愤怒的小鸟

题目大意

◇题目传送门◆

分析

看到$N$这么小，我们很容易想到状压或者是爆搜。。。

设$l(i,j)$为经过猪$i$和猪$j$的抛物线能够击中的猪的集合。

设$f(S)$为击中$S$中的猪所需的最少的鸟的数量。则有以下两种转移：

• 只发射击中猪$i$的鸟：f(S∪{i})=min?(f(S)+1)f(S\cup \{i\})=\min(f(S) + 1)f(S∪{ i})=min(f(S)+1)；
• 找另外一只猪$j$，发射从猪$i$到猪$j$的鸟，击中线上的所有点：$f(S\cup l(i,j))=\min (f(S)+1)$。

但这样的复杂度是$O(T{N}^2{2}^N)$的，这样做是过不了的，所以必须考虑优化。

考虑第一只不属于集合$S$中的猪$i$，我们强制必须首先击中这只猪，然后转移。

因为若我们不击中这只猪，后面就必须再倒回来射这只猪，也就是后面没射的猪的转移都是多余的。所以这样转移就可以节省时间。

这样加上一个小的优化，复杂度就能够减少到$O(TN{2}^N)$了，就能够通过这道题。

参考代码

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int Maxn = 18;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-6;int N;
double X[Maxn + 5], Y[Maxn + 5];
int line[Maxn + 5][Maxn + 5];
int f[(1 << Maxn) + 5];inline void solve(double &x, double &y, double a1, double b1, double c1,double a2, double b2, double c2) {
    y = (a1 * c2 - a2 * c1) / (a1 * b2 - a2 * b1);x = (c1 - b1 * y) / a1;
}int main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint _;scanf("%d", &_);while(_--) {
    scanf("%d %*d", &N);for(int i = 1; i <= N; i++)scanf("%lf %lf", &X[i], &Y[i]);memset(line, 0, sizeof line);memset(f, 0x3f, sizeof f);for(int i = 1; i <= N; i++)for(int j = 1; j <= N; j++) {
    if(fabs(X[i] - X[j]) < EPS) continue;double a, b;solve(a, b, X[i] * X[i], X[i], Y[i], X[j] * X[j], X[j], Y[j]);if(a > -EPS) continue;for(int k = 1; k <= N; k++)if(fabs(a * X[k] * X[k] + b * X[k] - Y[k]) < EPS)line[i][j] |= (1 << (k - 1));}f[0] = 0;for(int s = 0; s < (1 << N); s++)for(int i = 1; i <= N; i++)if(!(s & (1 << (i - 1)))) {
    f[s | (1 << (i - 1))] = min(f[s | (1 << (i - 1))], f[s] + 1);for(int j = 1; j <= N; j++) {
    if(fabs(X[i] - X[j]) < EPS) continue;f[s | line[i][j]] = min(f[s | line[i][j]], f[s] + 1);}break;}printf("%d\n", f[(1 << N) - 1]);}return 0;
}