生日蛋糕
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外，以上所有数据皆为正整数）
Input
有两行，第一行为N（N <= 10000），表示待制作的蛋糕的体积为Nπ；第二行为M(M <= 20)，表示蛋糕的层数为M。
Output
仅一行，是一个正整数S（若无解则S = 0）。
Sample Input
100
2
Sample Output
68
Hint
圆柱公式
体积V = πR2H
侧面积A' = 2πRH
底面积A = πR2
Source
题目类型：DFS+剪枝
算法分析：这里需要从大到小独立枚举ri和hi，范围是下面圆柱体的ri-1到此时的层数(因为体积最小为1 * 1 * 1 + 2 * 2 * 2 + …… )。最后的表面积为对应层上圆柱体的2 * ri * hi再加上最下面一层的ri * ri的值。由于这里需要使用二重循环来枚举ri和hi，状态空间非常大，需要多个剪枝，其中一个剪枝是当前和sum已经大于minval了，第二个剪枝是当前剩下的体积比还没有制作的圆柱体的最小体积和还要小，最后一个剪枝是当前的sum+期望最小的表面积和比minval大了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
#pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e6 + 6666; int minval, n, m, cnt[66]; void dfs (int cur, int val, int ri, int hi, int sum) { if (cur == 0) { if (val == 0) minval = min (minval, sum); return ; } if (sum >= minval || val < cnt[cur-1] || 2 * val / ri + sum >= minval) return ; // cout << ri << " " << hi << endl; for (int i = ri - 1; i >= cur; i--) { int pa = min (hi - 1, (val - cnt[cur-1]) / i / i); for (int j = pa; j >= cur; j--) { if (val - i * i * j >= 0) { if (cur == m) dfs (cur - 1, val - i * i * j, i, j, sum + 2 * i * j + i * i); else dfs (cur - 1, val - i * i * j, i, j, sum + 2 * i * j); } } } } int main() { // CFF; memset (cnt, 0, sizeof (cnt)); for (int i = 1; i <= 22; i++) cnt[i] = cnt[i-1] + i * i * i; while (scanf ("%d %d", &n, &m) != EOF) { minval = INF; dfs (m, n, n + 6, n + 6, 0); if (minval == INF) puts ("0"); else printf ("%d\n", minval); } return 0; } |
- « 上一篇：poj2739
- poj3684：下一篇 »