poj1190 生日蛋糕

题意：

要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时，要求Ri > Ri+1且Hi > Hi+1。由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。令Q = Sπ 请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。（除Q外，以上所有数据皆为正整数）

思路：

深搜（枚举每一层的高度和半径）+剪枝

最优性剪枝：

搭建过程中预见到搭完后面积一定会超过目前最优表面积,则停止搭建。

可行性剪枝：

1.搭建过程中预见到再往上搭，高度已经无法安排，或者半径已经无法安排，则停止搭建。

2.搭建过程中发现还没搭的那些层的体积，最大也到不了还缺的体积，则停止搭建。（之前搭得太小）

3.搭建过程中发现还没搭的那些层的体积，一定会超过还缺的体积，则停止搭建。（之前搭得太大）

实现：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #define INF 0x3f3f3f3f
 5 using namespace std;
 6 int n, m;
 7 int min_now = INF;
 8 int minV[25];
 9 int minA[25];
10 
11 int cal2(int a)
12 {
13     return a * a;
14 }
15 
16 int cal3(int a)
17 {
18     return a * a * a;
19 }
20 
21 int maxV(int r, int h, int rem)
22 {
23     int ans = 0;
24     for (int i = 0; i < rem; i++)
25     {
26         ans += r * r * h;
27         r--, h--;
28     }
29     return ans;
30 }
31 
32 void dfs(int cur, int v, int r, int h, int s)
33 {
34     if (s + minA[cur] >= min_now)  //最优性剪枝 
35         return;
36     if (r - 1 < m - cur || h - 1 < m - cur) //可行性剪枝1（之后无法安排）
37         return;
38     if (maxV(r - 1, h - 1, m - cur) < v) //可行性剪枝2（之前搭的太小）
39         return;
40     if (v < minV[cur]) //可行性剪枝3（之前搭得太大）
41         return;
42     if (cur == m)
43     {
44         if (v == 0)
45         {
46             if (s < min_now)
47             {
48                 min_now = s;
49             }
50         }
51         return;
52     }
53     for (int i = h - 1; i >= 1; i--) // 枚举高度
54     {
55         for (int j = r - 1; j >= 1; j--) // 枚举半径
56         {
57             dfs(cur + 1, v - j * j * i, j, i, s + 2 * j * i);
58         }
59     }
60 }
61 
62 int main()
63 {
64     cin >> n >> m;
65     minV[0] = (1 + m) * m / 2;
66     minV[0] = minV[0] * minV[0];
67     minA[0] = m * (m + 1) * (2 * m + 1) / 3;
68     for (int i = 1; i < m; i++)
69     {
70         minV[i] = minV[i - 1] - cal3(m - i + 1);
71         minA[i] = minA[i - 1] - 2 * cal2(m - i + 1);
72     }
73     for (int i = sqrt(n) + 1; i >= m; i--)
74     {
75         for (int j = n / i / i; j >= m; j--)
76         {
77             dfs(1, n - i * i * j, i, j, i * i + 2 * i * j);
78         }
79     }
80     if (min_now == INF)
81         puts("0");
82     else
83         printf("%d
", min_now);
84     return 0;
85 }