蛋糕（深搜剪枝）

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


#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 25 , INF = 1e9;

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

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;
            R[u] = r,H[u] = h;
            dfs(u-1, v + r *r *h , s + 2 * r * h + t);
        }
    }
}

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= m; i ++)
    {
        mins[i] = mins[i-1] + i *i * 2;
        minv[i] = minv[i-1] + i * i * i;
    }
    
    R[m+1] = H[m+1] = INF;
    
    dfs(m,0,0);
    
   if(ans == INF)ans = 0;
  cout << ans << endl;
    
    return 0;
}

蛋糕（深搜 剪枝）

蛋糕（深搜剪枝）