手工蛋糕装饰品题解

时间: 2023-10-04 admin IT培训

手工蛋糕装饰品题解

手工蛋糕装饰品题解

原题链接:=1190
题目描述:
Lisa的生日快到了,Rose打算制作一个手工蛋糕装饰品送给Lisa。手工蛋糕装饰品每层都有一个圆柱体构成。假设从底层往上数,第i(1<= i <= K)层蛋糕是半径为Ri,高度为Hi的圆柱。当i < K时,要求Ri > Ri+1且Hi > Hi+1。Lisa为了美观,打算在蛋糕上涂色,为尽可能节约,Lisa希望蛋糕外表面(最下一层的下底面除外)的面积Q最小。令Q = Sπ
对给出的V和K,找出蛋糕的制作方案(适当的Ri和Hi的值),使S最小。(除Q外,以上所有数据皆为正整数)

输入
循环输入两行,第一行数据V(V <= 10000),代表手工蛋糕装饰品的体积为Vπ;第二行数据K(K<= 20),代表手工蛋糕为K层。

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

输入样例:
100
2
1
1

输出样例:
68
3

Hint:
圆柱公式
体积V = πR2H
侧面积A’ = 2πRH
底面积A = πR2

题解:
这道题是典型的DFS,需要剪枝否则会超时, 前两个剪枝很好想, 但是第三个剪枝不太好想。 当前的解加上剩余最优解如果大于最优解就剪枝。 有很多细节需要注意, 比如说需要一个minv保存前i层的最小体积,(因为从上到下不管是r 还是 h 都是严格单调递增的!!!)当dep == m 的时候将 tmp 初始化为r * r , 回溯的时候就应该当初始化为 0。代码都有注释。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <algorithm>
#include <set>
#define INF 0x3fffffff
using namespace std;int ans; // 保存临时最优解
int minv[21]; // 前 i 块蛋糕的最小体积( 从上到下 )
int tmp; // 保存当前表面积
int n, m;void Init() {memset( minv, 0, sizeof( minv ) );for( int i = 1; i <= 20; i++ ) {minv[i] = minv[i-1] + i * i * i;}
}void dfs( int v, int dep, int R, int H ) {//剩余体积,当前深度,当前的半径,当前的高if( dep == 0 ) {if( v == 0 && ans > tmp ) {// 只有当体积正好为0的时候才能更新ans(就是说正好满足n体积&&m层)ans = tmp;}return;
}
// 如果剩余体积小于最小体积(蛋糕不能到m层) 或者当前解已经比最优解大或者当前解 + 剩余部分的最优解比最优解大,剪枝
if( v - minv[dep-1] < 0 || tmp >= ans || 2 * v / R + tmp >= ans ) return;     
// 因为这是从底向上遍历的,所以r and h 都不会小于 dep                                                           
for( int r = R - 1; r >= dep; r-- ) {  int Hm = min( H - 1, ( v - minv[dep-1] ) / r / r );for( int h = Hm; h >= dep; h-- ) {if( v - r * r * h >= 0 ) {// 如果深度为 m 的话则表面积为最下面一块的上表面,这样以后只需要增添侧表面积就可以了if( dep == m ) tmp = r * r;  tmp += 2 * r * h;dfs( v - r * r * h, dep - 1, r, h );tmp -= 2 * r * h; // 回溯if( dep == m ) tmp = 0;}}}return;
}
int main() {Init();  //建立一个储存前 i 层最小体积的数组while( cin >> n >> m ) {ans = INF;dfs( n, m, n + 1, n + 1 ); // 后面的两个 n + 1 只是保证足够大printf("%d\n",ans==INF?0:ans);}return 0;
}