标签： 状压DP

$$ \text{设}state\text{是还没死的猪的集合。} \\ \text{转移时，首先考虑一条抛物线只打一头猪的情况，然后转移。} \\ \text{然后再考虑两头猪连成一条抛物线的情况，然后判断一下其他哪些猪也在这条抛物线上} \\ \text{然后转移。} \\ \text{这样做的复杂度是}O\left( T\times n^3\times 2^n \right) \\ \text{在}luogu\text{会}TLE\text{两个点。} \\ \text{考虑优化枚举两头猪连成一条抛物线的过程。} \\ \text{先处理出来一个数组}sets\left[ i \right] \left[ j \right] \text{，表示经过第}i\text{头和第}j\text{头猪的抛物线可以打下来的猪的集合。} \\ \text{然后转移的复杂度可以优化到}O\left( T\times n^2\times 2^n \right) \\ \text{然后}luogu\ AC,LOJ\ AC $$

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>
#include <assert.h>
using int_t = long long int;

using real_t = double;

using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = (1 << 20) - 1;
const int_t INF = 0x7fffffff;
const real_t EPS = 1e-6;
template <class T>
T fabs(T x)
{
    if (x < 0)
        return -x;
    return x;
}
template <class A, class B>
auto fcmp(A a, B b) -> decltype(a - b)
{
    if (fabs(a - b) < EPS)
        return 0;
    return a - b;
}
struct Processor
{
    struct Pig
    {
        real_t x;
        real_t y;
        int_t bit;
    } pigs[20];
    int_t n, m;
    //经过i j 两个点抛物线所能打下来的猪的集合
    int_t sets[20][20];
    int_t memory[LARGE];
    bool visited[LARGE];
    int_t search(int_t state)
    {
        if (state == 0)
            return 0;
        if (visited[state])
            return memory[state];
        auto &result = memory[state];
        visited[state] = true;
        result = INF;
        std::vector<Pig> alive;
        for (int_t i = 0; i < n; i++)
        {
            if (state & (1 << i))
            {
                //考虑一条抛物线打一头猪
                result = std::min(search(state ^ (1 << i)) + 1, result);
                alive.push_back(pigs[i]);
                alive.back().bit = i;
            }
        }
        //考虑任何两头猪构成的抛物线
        for (int_t i = 0; i < alive.size(); i++)
        {
            for (int_t j = i + 1; j < alive.size(); j++)
            {
                if (sets[alive[i].bit][alive[j].bit])
                {
                    result = std::min(result, search(state & (~sets[alive[i].bit][alive[j].bit])) + 1);
                }
            }
        }
        return result;
    }

    int_t processs()
    {

        cin >> n >> m;
        for (int_t i = 0; i < n; i++)
        {
            cin >> pigs[i].x >> pigs[i].y;
        }
        for (int_t i = 0; i < n; i++)
        {
            for (int_t j = i + 1; j < n; j++)
            {
                auto &curr = sets[i][j];
                curr = 0;
                real_t x1 = pigs[i].x, y1 = pigs[i].y;
                real_t x2 = pigs[j].x, y2 = pigs[j].y;
                if (x1 == x2)
                    continue;
                real_t a = ((y1 / x1) - (y2 / x2)) / (x1 - x2);
                if (a >= 0)
                    continue;
                real_t b = ((y1 / (x1 * x1)) - (y2 / (x2 * x2))) / ((1 / x1) - (1 / x2));
                for (int_t k = 0; k < n; k++)
                {
                    auto &currp = pigs[k];
                    if (fabs(currp.y - (currp.x * currp.x * a + currp.x * b)) <= EPS)
                    {
                        curr ^= (1 << k);
                    }
                }
            }
        }
        std::fill(visited, visited + LARGE, false);
        return search((1 << n) - 1);
    }
};

int main()
{
    int_t T;
    cin >> T;
    for (int_t i = 1; i <= T; i++)
    {
        auto p = new Processor;
        cout << p->processs() << endl;
        delete p;
    }
    return 0;
}