首页 > 代码库 > POJ 1190 生日蛋糕 DFS

POJ 1190 生日蛋糕 DFS

生日蛋糕
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 18225   Accepted: 6486

Description

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 = πR2
侧面积A‘ = 2πRH 
底面积A = πR2 
 

   题目分析: 以前做过一次, 但是智障的我还是忘了, 这次写废了很大的劲儿, 发现还是有很多东西自己想不到, 这道题是典型的DFS,需要剪枝否则会TLE, 前两个剪枝很好想, 但是第三个剪枝不好想( 自己干想, 看题解一下就明白了, 这是病, 得治 )。 当前的解加上剩余最优解如果大于最优解就剪枝。 有很多细节需要注意, 比如说需要一个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;
    }
    if( v - minv[dep-1] < 0 || tmp >= ans || 2 * v / R + tmp >= ans ) return; // 如果剩余体积小于最小体积( 蛋糕不能到 m 层 ) 或者 当前解已经比最优解大
                                                                            //  或者当前解 + 剩余部分的最优解比最优解大 , 剪枝, 神剪枝
    for( int r = R - 1; r >= dep; r-- ) {  // 因为这是从底向上遍历的, 所以r and h 都不会小于 dep
        int Hm = min( H - 1, ( v - minv[dep-1] ) / r / r );
        for( int h = Hm; h >= dep; h-- ) {
            if( v - r * r * h >= 0 ) {
                if( dep == m ) tmp = r * r;  // 如果深度为 m 的话则表面积为最下面一块的上表面, 这样以后只需要增添侧表面积就可以了
                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 只是保证足够大
        cout << ans << endl;
    }
    return 0;
}
View Code

 

 

  看来自己的做过的题还是要重做, 多想, 然后就是果然题量不能说明一切, 思想才是最重要的 ,只有思想搞上来了才不会沦为码农, 多看书, 多培养自己的思维, 代码量固然要够, 但是能够安安静静的看书的时间大部分都在大学中, 所以适当的调整方向, 人一我十, 人十我万!!!

POJ 1190 生日蛋糕 DFS