参考文献
random_srand大佬的代码注释
C++ 代码
//每日一题 4
//2022-3-31
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>//error: sqrt库函数
using namespace std;
const int M = 30, INF = 1e9;
int n, m, s;
//res是最小表面积(提取了pi)
//因为求最小值,所以初始化为INF
int res = INF;
//mins[i]是第1层到第i层的 侧面积(提取了pi)之和的 最小值,
//minv[i]是第1层到第i层的 体积(提取了pi)之和的 最小值
int mins[M], minv[M];
//R[i]是第i层的半径
//H[i]是第i层的高
int R[M], H[M];
/*
从顶层到底层,为每层分别编号1, 2, ... , m
从顶层到底层,半径分别是R1, ..., Rm
从顶层到底层,高分别是H1, ..., Hm
以上数据全部是正整数
因为从体积公式,面积公式中提取了pi,所以
N = R1 * R1 * H1 + R2 * R2 * H2 + ... + Rm * Rm * Hm
S = R1 * R1 + 2 * (R1 * H1 + ... + Rm * Hm)
从底层(m层)开始向上搜索,积累的体积是Vcur,表面积是Scur
Vcur = Rm * Rm * Hm + ... + Ru+1 * Ru+1 * Hu+1
Scur = 2 * (Rm * Hm + ... + Ru+1 * Hu+1)
从顶层(1层)到u层的侧面积之和
S(1 ~ u) = 2 * (R1 * H1 + ... + Ru * Hu)
N - Vcur = R1 * R1 * H1 + R2 * R2 * H2 + ... + Ru * Ru * Hu
S(1 ~ u) > (2 / Ru+1 * (N - Vcur))
*/
/*
u是当前搜索的层号,尝试构造Ru和Hu
v是当前已经构造的体积, 即m到u+1层的体积
s是当前已经构造的面积,即m到u+1层的面积
*/
void dfs (int u, int v, int s)
{
//剪枝1: 可行性, 当前体积Vcur太大,剪
if (v + minv[u] > n) return ;
//剪枝2: 最优性,从当前侧面积Scur加上顶部u层的最小侧面积,不比当前res更优,剪
if (s + mins[u] >= res) return ;
//剪枝3: 最优性剪枝,从当前侧面积Scur 加上 一个小于顶部u层的侧面积的值 也大于等于当前res,
//不比当前res更优,剪
if (s + 2 * (n - v) / R[u + 1] >= res) return ;
//搜索结束
if (u == 0) {
if (v == n)
res = s;
return ;
}
//剪枝4: 可行性剪枝,Ru和Hu的上下界
//剪枝5: 优化搜索顺序,先R再H,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, (int)((n - v - minv[u-1]) / (r * r)) ); h >= u; h--) {
R[u] = r, H[u] = h;
//俯视图中,所有圆环面积 + 顶层圆盘面积 == 底层圆盘面积
int t = (u == m) ? r * r : 0;
dfs(u - 1, v + r * r * h, s + 2 * r * h + t);
}
}
}
int main()
{
//scanf可以跨行
scanf("%d%d", &n, &m);
//printf("%d %d", n, m);
for (int i = 1; i <= m; i++) {
//提取pi后,体积是r * r * h, 面积是 r * r
//第i层中r和h的最小值都是i
minv[i] = minv[i-1] + i * i * i;//圆柱体积
mins[i] = mins[i-1] + 2 * i * i;//圆柱侧面积
}
R[m+1] = INF, H[m+1] = INF;
dfs(m, 0, 0);
if (res == INF)
res = 0;
cout << res << endl;
return 0;
}