算法提高课汇总

算法思路

题目给我们一个体积为$N$, 层数为$M$的生日蛋糕🎂.

自底向上, 每层蛋糕的半径和高度严格上升. 由于第1层蛋糕高度和半径至少为$1$, 第$m$层蛋糕
的高度和半径至少为$m$. 计算蛋糕表面积和体积时不需要考虑$\pi$.

考虑表面积时, 除底层需要额外考虑柱体圆的面积, 其他层只需要考虑侧面积.

搜索顺序

枚举每一层蛋糕的半径以及高度.

剪枝优化

1. 优化搜索顺序

1. 底层蛋糕的体积更大, 按层自底向上的顺序枚举蛋糕.

2. 圆柱体体积$V = r^2\times h$, $r$对体积影响更大, 在枚举某一层时, 先枚举半径再枚举体积,
   且均从大到小枚举.

$\;\;\;\;$第$u$层蛋糕半径与高度的范围:

• 半径: 由于自底向上每层蛋糕的半径严格递增, $u\le R(u)\le R(u + 1) - 1$. 假设$u + 1\sim m$层
  蛋糕的体积为$v$, 有$R(u)^2\times h\le n - v$, $h\ge u$ --> $R(u)\le \sqrt{(n - v)/u}$.
  --> $u\le R(u)\le min\lbrace R(u + 1) - 1, \sqrt{(n - v)/u}\rbrace$.

• 高度: 由于自底向上每层蛋糕的高度严格递增, $u\le H(u)\le H(u + 1) - 1$. 假设$u + 1\sim m$层
  蛋糕的体积为$v$, $r^2\times H(u)\le n - v$, (先枚举$r$, 此时$r$已经确定)
  --> $u\le H(u)\le min\lbrace H(u + 1) - 1, (n - v) / r^2\rbrace$.

2. 可行性 $\&$ 最优性剪枝

1) 预处理前$u$层体积与面积的最小值之和(第$u$层的半径与高度均取最小值$u$): $minv(u) \& mins(u)$.
$\;\;\;\;$(类似$A^*$算法中的估价函数)

• 若$u + 1\sim m$层蛋糕的体积之和为$v$, 则必须满足$v + minv(u)\le n$, 否则可以直接返回.(可行性)

• 若$u + 1\sim m$层蛋糕的表面积之和为$s$, 则必须满足$s + mins(u)\lt ans$, 否则可以直接返回.(最优性)
  $ans$指的是当前最优解.

2) $1\sim u$层蛋糕的表面积之和为$s_{1\sim u} = \sum_{k = 1}^{u} 2R_k\times H_k$.
$\;\;\;\;\;\;\;$$1\sim u$层蛋糕体积$v_{1\sim u} = n - v = \sum_{k = 1}^{u} R_k^2\times H_K$.
$\;\;\;\;\;\;\;$进一步对$s_{1\sim u}$处理, $s_{1\sim u} = \frac{2}{R(u + 1)}\times \sum_{k = 1}^{u}R_k\times H_k\times R(u + 1)$,
$\;\;\;\;\;\;\;$由于$R(u + 1)\gt R(u)\gt R(u - 1)\gt …$, $s_{1\sim u}\gt \frac{2}{R(u + 1)}\times \sum_{k = 1}^{u}R_k^2\times H_k$
$\;\;\;\;\;\;\;= \frac{2}{R(u + 1)}\times (n - v)$.
$\;\;\;\;\;\;\;$假设$u + 1\sim m$层表面积之和为$s$, 则$s + s_{1\sim u}\gt s + \frac{2}{R(u + 1)}\times (n - v)$
$\;\;\;\;\;\;\;$即$s + \frac{2}{R(u + 1)}\times (n - v)$是当前表面积和的下限.
$\;\;\;\;\;\;\;$若$s + \frac{2}{R(u + 1)}\times (n - v)\ge ans$, 可直接返回.(最优性)

具体代码

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

using namespace std;

const int M = 25, INF = 1e9;

int n, m;
int H[M], R[M];
int minv[M], mins[M];
int ans = INF; 

void dfs(int u, int v, int s)
{
    if (v + minv[u] > n)    return; //可行性剪枝
    if (s + mins[u] >= ans )    return; //最优性剪枝
    if (s + 2 * (n - v) / R[u + 1] >= ans ) return; //最优性剪枝

    if (!u)
    {
        if (v == n) ans = s; //第0层时 minu[0] = 0, 若s + 0 >= ans, 函数直接返回
        return;
    }

    for ( int r = min(R[u + 1] - 1, (int)sqrt((n - v) / u)); r >= u; r -- )
        for ( int h = min(H[u + 1] - 1, (n - v) / r / r); h >= u; h -- )
        {
            int t = 0;
            if ( u == m )   t = r * r; //额外考虑圆形表面积
            R[u] = r, H[u] = h;
            dfs(u - 1, v + r * r * h, s + t + 2 * r * h);
        }
}

int main()
{
    cin >> n >> m;

    //预处理前u层最小体积与面积之和
    for ( int i = 1; i <= m; i ++ )
    {
        minv[i] = minv[i - 1] + i * i * i; //r * r * h
        mins[i] = mins[i - 1] + 2 * i * i; //2 * r * h
    }

    H[m + 1] = R[m + 1] = INF; //哨兵 在第m层会被使用
    dfs(m, 0, 0);

    if ( ans == INF )   ans = 0;
    cout << ans << endl;

    return 0;
}