题目描述

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

设从下往上数第i层蛋糕是半径为Ri, 高度为Hi的圆柱。

当i < M时，要求Ri > Ri+1且Hi > Hi+1。

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

令Q = Sπ ，请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。

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

输入格式
输入包含两行，第一行为整数N（N <= 10000），表示待制作的蛋糕的体积为Nπ。

第二行为整数M(M <= 20)，表示蛋糕的层数为M。

输出格式
输出仅一行，是一个正整数S（若无解则S = 0）。

数据范围
1≤N≤10000,
1≤M≤20

输入样例：
100
2
输出样例：
68

算法 DFS + 剪枝 时间复杂度O(?)

很容易发现蛋糕的表面积等于 $(\sum_{i=1}^{m} 2r_ih_i) + r_m^2 * h_m $
体积等于 $\sum_{i=1}^{m} r_i^2h_i$

暴力枚举每一层的高度和半径

鬼畜剪枝的推导：
k为当前层
$ S_{剩余层的表面积} = \sum_{i=1}^{k}{2r_ih_i}$
提出一个 2 * $r_{k+1}$
$S_{剩余层的表面积} = 2 * (1/r_{k+1}) * \sum_{i=1}^{k}{r_{k+1}r_ih_i}$
显然
$V_{剩余层的体积} = \sum_{i=1}^{k} r_i^2h_i <= \sum_{i=1}^{k}{r_{k+1}r_ih_i}$
因为我们要得出剩余层的最小表面积，所以可以把V替换为那个式子
最后得到了我们的最终剪枝公式
$if(S_{当期} + 2 * (n - v) / R[u + 1] >= res) return$

最后发现写代码原来才是最简单的~。~，推导要死个人~。·

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

using namespace std;

const int N = 25,INF = 1e9;

int n,m;

int res = INF;

int minv[N],mins[N];
int h[N],r[N];

void dfs(int u,int s,int v)
{
    if(v + minv[u] > n) return;
    if(s + mins[u] >= res) return ;
    if(s + 2*(n-v)/r[u+1] >= res) return;
    if(u==0)
    {
        if(v==n) res=s;
        return;
    }

    for(int i=min(r[u+1]-1,(int)sqrt(n-v));i>=u;i--)
        for(int j=min(h[u+1]-1,(n-v)/i/i);j>=u;j--)
        {
            r[u]=i;
            h[u]=j;
            if(u==m)
                dfs(u-1,s+2*i*j+i*i,v+i*i*j);
            else
                dfs(u-1,s+2*i*j,v+i*i*j);
        }

}


int main(){

    cin >> n >> m;

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

    h[m+1] = r[m+1] = INF;

    dfs(m,0,0);

    if(res!=INF)
        cout << res << endl;
    else
        puts("0");

    return 0;
}