题目描述

7 月 17 日是 Mr.W 的生日，ACM-THU 为此要制作一个体积为 $N\pi$ 的 $M$ 层生日蛋糕，每层都是一个圆柱体。

设从下往上数第 $i$层蛋糕是半径为 $R_i$，高度为 $H_i$ 的圆柱。当 $i \lt M$ 时，要求 $R_i \gt R_{i+1}$ 且 $H_i \gt H_{i+1}$。

由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积 $Q$ 最小。

请编程对给出的 $N$ 和 $M$，找出蛋糕的制作方案（适当的 $R_i$ 和 $H_i$ 的值），使 $S$ 最小。

除 $Q$ 外，以上所有数据皆为正整数

输入格式

第一行为一个整数 $N$，表示待制作的蛋糕的体积为 $N\pi$。

第二行为 $M$，表示蛋糕的层数为 $M$。

数据范围

$1≤N≤10000,$
$1≤M≤20$

输出格式

输出一个整数 $S$，若无解，输出 $0$。

输入样例

100
2

输出样例

68

#include <cmath>
#include <iostream>

using namespace std;

const int N = 25, INF = 1e9;

int n, m;
int H[N], R[N];
int minv[N], mins[N];
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;
        return;
    }

    for (int r = min(R[u + 1] - 1, (int)sqrt(n - v)); 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;
            H[u] = h, R[u] = r;
            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;
    }

    R[m + 1] = H[m + 1] = INF;

    dfs(m, 0, 0);

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

    return 0;
}