P2831:愤怒的小鸟题解

思路

这一题是一道状压 DP（见数据范围）。我们把猪的死活压缩起来作为状态，整个程序从\(0\)开始计数，可以推出以下几个方程：\(f[stat|(1<<i)] = min(f[stat|(1<<i)], f[stat] + 1)\)和\(f[stat|dotset[i][j]] = min(f[stat|dotset[i][j]],f[stat]+1)\)，其中dotset为经过点\(i,j\)的抛物线的点集。这个算法是\(O(Tn^2 2^n)\)，不够优秀。我们可以使用一个方法把\(n^2\)化为\(n\)。我们可以预先处理出每一个状态下第一个健在猪的编号，然后我们只要转移这一只猪即可，因为未来的猪都会被处理，所以可以直接降维。

代码

// P2831.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define pr pair<double, double>
using namespace std;
const double eps = 1e-8;
int T, n, dotset[19][19], dp[(1 << 19)], lbit[(1 << 19)], m;
pr prs[20];
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()
{
    for (int i = 0; i < (1 << 18); i++)
    {
        int bit = 0;
        for (; bit < 18 && (i & (1 << bit)) ; bit++)
            ;
        lbit[i] = bit;
    }
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        memset(dp, 0x3f, sizeof(dp)), memset(dotset, 0, sizeof(dotset));
        for (int i = 0; i < n; i++)
            scanf("%lf%lf", &prs[i].first, &prs[i].second);
        // process the curves;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                if (fabs(prs[i].first - prs[j].first) < eps)
                    continue;
                double a, b;
                solve(a, b, prs[i].first * prs[i].first, prs[i].first, prs[i].second,
                      prs[j].first * prs[j].first, prs[j].first, prs[j].second);
                if (a > -eps)
                    continue;
                for (int k = 0; k < n; k++)
                    if (fabs(a * prs[k].first * prs[k].first + b * prs[k].first - prs[k].second) < eps)
                        dotset[i][j] |= (1 << k);
            }
        dp[0] = 0;
        for (int stat = 0; stat < (1 << n); stat++)
        {
            int esspt = lbit[stat];
            dp[stat | (1 << esspt)] = min(dp[stat | (1 << esspt)], dp[stat] + 1);
            for (int k = 0; k < n; k++)
                dp[stat | dotset[esspt][k]] = min(dp[stat | dotset[esspt][k]], dp[stat] + 1);
        }
        printf("%d\n", dp[(1 << n) - 1]);
    }
    return 0;
}