算法提高课汇总

算法思路

题意理解

用最少的形如$y = ax^2 + bx$的抛物线消灭所有小猪(经过其坐标点), 我们只需要考虑选择经过
至少一只小猪的抛物线. 抛物线函数需要两头小猪确定, 我们可以枚举所有$n^2$个小猪对以计算所有
可能的抛物线, 并计算每条抛物线经过的所有小猪. 再确定一种算法选择抛物线最少的方案.

抛物线计算

首先考虑抛物线特点:

• 开口向下: $a\lt 0$.
• 不能垂直, 即$a\gt -\infty$. 也就是不能通过在同一垂直线的两点.

接着考虑给定两猪坐标:$(x_1, y_1), (x_2, y_2)$, 如何计算$a, b$.

$\begin{cases} y_1 = ax_1^2 + bx_1 \\\ y_2 = ax_2^2 + bx_2 \\\ \end{cases}$-->$\begin{cases} a = \frac{y_1/x_1 - y_2/x_2}{x1 - x2} \\\ b = \frac{y_1}{x_1} - ax_1 \\\ \end{cases}$

$DP$分析

集合类的状态压缩$DP$: 当前消灭的所有小猪作为集合, 以当前状态能转移到哪个状态作为状态计算方式.

状态表示 $dp(s)$

• 集合: 消灭小猪的集合为$s$的所有抛物线的选择方案.

• 属性: Min抛物线数目

状态计算

计算方式: 设当前状态为$s$, 取$s$中没有消灭的小猪, 用$s$加上能够消灭小猪的抛物线的消灭小猪集合,
作为新的状态$s’$, 用当前状态$s$更新$s’$.

为什么只需任意取一个$s$中没有消灭的小猪即可? 如果以该小猪所确定的抛物线$path_i$不在最优解中咋办?

• 因为可以证明通过第$i$个小猪计算出来的所有抛物线$path_i$一定存在一个在最优解之中. 假想一个案例:

  对于第1个小猪(相比后面的小猪, 我们总考虑它), 假设我们通过第一个小猪直接计算的
  抛物线(利用上面的公式带入第一个小猪坐标计算出的抛物线)最多只能通过$2$个小猪.
  而一条通过第7和第9个小猪的抛物线, 也通过第1个小猪, 也就是这条抛物线通过了$3$个小猪!
  那么这条抛物线应该才是我们考虑的最优解吧? 但是实际上这是不会发生的: 在计算小猪对$(1, 7)$
  时, 这条抛物线已经被计算过了! 而最优解是一个抛物线集合而不考虑顺序, 所以可以保证按
  从小到大的顺序一定能计算出最优解.

代码实现

浮点数运算

注意浮点数判断相等时可能会有一定误差, 需要一个合适的误差范围.

具体代码

#include <cmath>
#include <cstring>
#include <iostream>

#define x first
#define y second

using namespace std;

typedef pair<double, double> pdd;

const int N = 18, S = 1 << 18;
const double eps = 1e-6; //误差范围

int n, m;
pdd points[N];
int path[N][N]; //path[i][j]: 由小猪对(i, j)确定的直线所通过的小猪集合
int dp[S];

double cmp(double a, double b)
{//比较浮点数a, b大小. a > b : 返回1; a == b: 返回0; a < b: 返回-1
    if( fabs(a - b) < eps )
        return 0;
    if( a < b )
        return -1;
    return 1;
}

int main()
{
    int T;
    cin >> T;
    while( T -- )
    {
        cin >> n >> m;
        for( int i = 0; i < n; i ++ )   cin >> points[i].x >> points[i].y;

        //计算所有抛物线
        memset(path, 0, sizeof path);
        for( int i = 0; i < n; i ++ )
        {
            for( int j = 0; j < n; j ++ )
            {
                if( i == j )
                {
                    path[i][i] = 1 << i; //只经过一个点
                    continue;
                }

                double x1 = points[i].x, y1 = points[i].y;
                double x2 = points[j].x, y2 = points[j].y;
                if( !cmp(x1, x2) )  continue; //在同一垂直线上

                double a = (y1/x1 - y2/x2) / (x1 - x2);
                double b = y1 / x1 - a * x1;
                if( cmp(a, 0) >= 0 )    continue; // 不满足a < 0

                for( int k = 0; k < n; k ++ )
                {//计算通过小猪的集合
                    double x = points[k].x, y = points[k].y;
                    if( !cmp(a * x * x + b * x, y) )    
                        path[i][j] += 1 << k;
                }
            }
        }

        //dp
        memset(dp, 0x3f, sizeof dp);
        dp[0] = 0;
        for( int s = 0; s < 1 << n; s ++ )
        {
            int p = 0;
            for( int i = 0; i < n; i ++ )
            {
                if( !(s >> i & 1) )
                {
                    p = i;
                    break;
                }
            }

            for( int i = 0; i < n; i ++ )
            {
                int s1 = s | path[p][i];
                dp[s1] = min( dp[s1], dp[s] + 1 );
            }
        }
        cout << dp[(1 << n) - 1] << endl;
    }

    return 0;
}