POJ 1190 生日蛋糕剪枝

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

Hint

圆柱公式
体积V = πRH
侧面积A' = 2πRH
底面积A = πR

Source

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<sstream>

#include<algorithm>

#include<queue>

#include<deque>

#include<iomanip>

#include<vector>

#include<cmath>

#include<map>

#include<stack>

#include<set>

#include<fstream>

#include<memory>

#include<list>

#include<string>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

#define MAXN 2147483648

#define N 33

#define MOD 1000000

#define INF 1000000009

const double eps = 1e-;

const double PI = acos(-1.0);

/*

给定一个蛋糕的体积 和层数

求减去下底面后蛋糕表面积的最小值

从底层向上枚举，枚举每一层的可行H和R（加上之后小于V的）

当枚举到最后一层， 和最优解比较取值

*/

int V, M, ans = ;//体积和层数

void DFS(int level, int preh, int prer, int sumv, int sumS)

{

    if (sumv > V)return;

    if (ans && sumS > ans) return;

    //cout << "R:: " << prer << "    H:: " << preh << endl;

    if (level > M)

    {

        /*if (sumv == V)

        {

            cout << "SUMV " << sumv << "  SUMS  " << sumS << endl;

        }*/

        if (sumv == V)

        {

            if (!ans || ans > sumS)

                ans = sumS;

        }

        return;

    }

    for (int r = M-level+;r < prer; r++)

    {

        for (int h = M-level+; h < preh; h++)

        {

            if (ans && sumS + r**h > ans)continue;

            if (sumv + (M - level + )*h*r*r < V ) continue;

            if (ans && sumS +  * (V - sumv) / r > ans) continue;//当前面积 加上剩余体积的最大面积

            if (sumv + h*r*r <= V)

                DFS(level + , h, r, sumv + h*r*r, sumS +  * r*h);

        }

    }

}

int main()

{

    scanf("%d%d", &V, &M);

    for (int r = M; r <= ; r++)

    {

        for (int h = M; h <= ; h++)

        {

            if (r*r*h*M < V|| r*r*h>V) continue;

            DFS(, h, r, r*r*h, r*r +  * r*h);

        }

    }

    printf("%d\n", ans);

}

蛋糕

POJ 1190 生日蛋糕 剪枝

POJ 1190 生日蛋糕剪枝