题目链接

思路

大体思路

记最底层为m,很容易观察得出，表面积的公式为
$$S_总 = S_{m层上侧面积} + \sum_{i=1}^{m}2\pi R_iH_i$$
而体积为
$$V_总= \sum_{i=1}^{m}\pi R_i^2H_i$$

有了两个公式，还有题目给出的每层最小高度和最小半径，就知道可以用剪枝+暴搜来做这个题

图示

这个图对理解下面公式有帮助

剪枝优化

1.优化搜索顺序

1. 层间：从下到上
2. 层内：先枚举半径再枚举高（半径相对于高来说对体积的影响较大），半径由大到小，高度由大到小

2. 可行性剪枝

记总体积为n，当前层位u, 第u层的高度为$H_u$, 半径为$R_u$， 体积为$V_u$, 第$m$层到第u层体积的累计值$V$

1. 对于R, 当前为第u层, 第u层的体积为$V_u$。R最小的取值应该是当前的层号u ，R的最大值应该由两部分决定
   • u+1层的半径减1, 记$R_{u+1}-1$
   • 第u层体积的最大值除第u层高度的最小值u

这两者的最小值, 故有以下等式成立
$$ u \leq R_u \leq min \lbrace R_{u+1}-1, \sqrt{\frac{n-min\sum_{i=1}^{u-1}V_i - V}{u}} \rbrace$$

1. 对于第u层高度h的推导同理，高度h的取值的最小值应该大于等于层号u，高度的最小值由两部分决定
   • $H_{u+1}-1$
   • 第u层体积的最大值除第u层的底面积最小值

故同理可得出下列等式
$$ u \leq H_u \leq min \lbrace H_{u+1}-1, \frac {{n-min\sum_{i=1}^{u-1}V_i - V}}{R_u^2} \rbrace$$

1. 考虑体积的剪枝：预处理前u层的体积最小值$min\sum_{i=1}^{u-1}V_i$, 会有$V + min\sum_{i=1}^{u-1}V_i \leq n$

2. 推表面积公式和体积公式的关系

   第一层到第u层的表面积有（不考虑$\pi$）
   $$S_{1-u} = 2\sum_{i=1}^{u}R_iH_i = \frac{2}{R_{u+1}} \sum_{i=1}^{u}R_{u+1}R_iH_i > \frac{2}{R_{u+1}}\sum_{i=1}^{u}R_i^2H_i$$
   第一层到第u层的体积有
   $$n - V = \sum_{i=1}^{u}R_i^2H_i$$
   所以惊奇地发现
   $$S_{1-u} >\frac{2(n-V)}{R_{u+1}}$$
   因此$S_总=S + S_{1-u}>=S_{ans}$，即$S + \frac{2(n-V)}{R_{u+1}} >= S_{ans}$时就可以剪枝掉（最优性剪枝)

   3.最优性剪枝

   记第$m$层到第u层表面积的累计值$S$, 第1到第$u-1$层表面积的最小值为 $min\sum_{i=1}^{u-1}S_i$
   则应该有$S + min\sum_{i=1}^{u-1}S_i < res$

   4.排除等效冗余

   至此，所有的剪枝都已经考虑清楚，码代码应该不是什么大问题

   代码

#include<iostream>
#include<cmath>
using namespace std;

const int N = 24, INF = 1e9;

int n, m;
int minv[N], mins[N];
int res = INF;

//记录每层的半径和高，因为会用到上一层的高度
int R[N], H[N];

//u当前层次，v当前处理的体积和，s当前处理的面积和
void dfs(int u, int v, int s)
{
    if(v + minv[u] > n) return;
    if(s + mins[u] >= res) return;
    if (s + 2 * (n - v) / R[u + 1] >= res) return;

    if(!u)
    {
        if(v == n) res = s;
        return;
    }

    //搜索顺序，先R后H，从大到小
    for(int r = min(R[u + 1] - 1,(int)sqrt((n - v - minv[u - 1]) / u)); r >= u; r--)
        for(int h = min(H[u + 1] - 1, (n - v - minv[u - 1]) / r / r); h >= u; h--)
        {
            H[u] = h, R[u] = r;

            //最底层的时候需要加上r*r
            int t = u == m ? r * r : 0;

            dfs(u - 1, v + r * r * h, s + 2 * r * h + t);
        }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        minv[i] = minv[i - 1] + i * i * i;
        mins[i] = mins[i - 1] + 2 * i * i;
    }

    //m+1层不存在，作为哨兵，减少边界情况的判断
    R[m + 1] = H[m + 1] = INF;

    dfs(m, 0, 0);

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


    return 0;
}