1190:生日蛋糕,深搜逻辑思路、枚举、剪枝

原题:http://bailian.openjudge.cn/practice/1190/

描述

7月17日是Mr.W的生日,ACM-THU为此要制作一个体积为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外,以上所有数据皆为正整数)

输入

有两行,第一行为N(N <= 10000),表示待制作的蛋糕的体积为Nπ;第二行为M(M <= 20),表示蛋糕的层数为M。

输出

仅一行,是一个正整数S(若无解则S = 0)。

样例输入

100
2

样例输出

68

解法

思路:这个题比较难想(至少对我这种菜鸟),整体思路是深搜+枚举,枚举每一层可能的高度和半径,搜索的范围是底层蛋糕的最大可能半径和最大可能高度。从底层往上搭蛋糕,半径和高度都是从大到小试。关键在于剪枝。

  • 最优性剪枝:超过目前最优表面积
  • 可行性剪枝:再往上搭的时候,高度或者半径已经无法安排
  • 可行性剪枝:搭建过程中发现还没搭的那些层的体积(最小的)一定会超过还缺的体积,说明前面搭多了
  • 可行性剪枝:搭建过程中发现还没搭的那些层的体积,最大也到不了还缺的体积,说明前面搭少了
 1 #include <iostream>
 2 #include <vector>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #define INF 1<<30
 7 using namespace std;
 8 int N, M;
 9 int minArea;//最优表面积
10 int area;//正在搭建中的蛋糕表面积
11 int minV[30];//minV[n]表示n层蛋糕最少的体积
12 int minA[30];//minA[n]表示n层蛋糕最少侧表面积
13 int MaxVforNRH(int n, int r, int h) {
14 //求在n层蛋糕,底层最大半径为r、最高高度为h的情况下,能凑出来的最大体积
15     int v = 0;
16     for (int i = 0; i < n; i++)
17         v += (r - i)*(r - i)*(h - i);
18     return v;
19 }
20 void dfs(int v, int n, int r, int h)
21 {//用n层去凑体积v,最底层半径不超过r,高度不超过h,求出最小表面积放入minArea
22     if (n == 0) {
23         if (v)
24             return;
25         else {
26             minArea = min(area, minArea);
27             return;
28         }
29     }
30     if (v <= 0)
31         return;
32     if (minV[n] > v)//还没搭的那些层的体积一定会超过还缺的体积,说明前面搭多了
33         return;
34     if (area + minA[n] >= minArea)//最优性剪枝
35         return;
36     if (h < n || r < n)//高度或者半径已经无法安排
37         return;
38     if (MaxVforNRH(n, r, h) < v)//搭建过程中发现还没搭的那些层的体积,最大也到不了还缺的体积,说明前面搭少了
39         return;
40     for (int rr = r; rr >= n; rr--) {
41         if (n == M)//底面积
42             area = rr * rr;
43         for (int hh = h; hh >= n; hh--) {
44             area += 2 * rr*hh;
45             dfs(v - rr * rr*hh, n - 1, rr - 1, hh - 1);
46             area -= 2 * rr*hh;//回溯
47         }
48     }
49 }
50 int main()
51 {
52     cin >> N >> M;
53     minV[0] = 0;
54     minA[0] = 0;
55     for (int i = 1; i <= M; i++) {
56         minV[i] = minV[i - 1] + i * i*i;
57         minA[i] = minA[i - 1] + 2 * i*i;
58     }
59     if (minV[M] > N)
60         cout << 0 << endl;
61     else {
62         //最底层体积不超过N-minV[M-1]
63         int maxH = (N - minV[M - 1]) / (M*M) + 1;//底层最大高度
64         int maxR = sqrt(double(N - minV[M - 1]) / M) + 1;//底层高度至少M
65         area = 0;
66         minArea = INF;
67         dfs(N, M, maxR, maxH);
68         if (minArea == INF)
69             cout << 0 << endl;
70         else
71             cout << minArea << endl;
72     }
73     return 0;
74 }

 

上一篇:3、数据分析--聚类项目分析


下一篇:[SDOI2009]HH的项链解题报告