链接:

https://www.acwing.com/problem/content/170/

题意:

7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。

设从下往上数第i层蛋糕是半径为Ri, 高度为Hi的圆柱。

当i < M时，要求Ri > Ri+1且Hi > Hi+1。

由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。

令Q = Sπ ，请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。

除Q外，以上所有数据皆为正整数。

思路:

搜索加剪枝.

从最下面的蛋糕开始处理, 枚举半径和高度,在范围内从大到小

考虑如果当前情况比最好情况还差, 则返回.

记录每层最少还需要多少体积的蛋糕, 当不够的时候返回.

考虑未来的表面积期望值, 若期望值较高, 也返回.

代码:

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int CntV[25], CntS[25];

int H[25], R[25];

int ans = INF;

int n, m;

void Dfs(int dep, int v, int s)

{

    if (s+CntS[dep] > ans)

        return ;

    if (n-v < CntV[dep])

        return ;

    if (2*(n-v) / R[dep+1]+s > ans)

        return ;

    if (dep == 0)

    {

        if (v == n)

            ans = min(ans, s);

        return;

    }

    for (int r = min((int)sqrt(n-v), R[dep+1]-1);r >= dep;r--)

    {

        for (int h = min((int)((n-v)/(r*r)), H[dep+1]-1);h >= dep;h--)

        {

            int t = 0;

            if (dep == m)

                t = r*r;

            R[dep] = r, H[dep] = h;

            Dfs(dep-1, v+r*r*h, s+2*r*h+t);

        }

    }

}

int main()

{

    for (int i = 1;i <= 20;i++)

    {

        CntV[i] = CntV[i-1]+i*i*i;

        CntS[i] = CntS[i-1]+2*i*i;

    }

    scanf("%d%d", &n, &m);

    H[m+1] = R[m+1] = 1e9;

    Dfs(m, 0, 0);

    if (ans == INF)

        printf("0\n");

    else

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

    return 0;

}

巴特西

Acwing-168-生日蛋糕(搜索, 剪枝)

链接:

题意:

思路:

代码:

最新文章

热门文章