问题描述

需要制作一个体积为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外,以上所有数据皆为正整数)。

输入

有两行,第一行为N(N <= 10000),表示待制作的蛋糕的体积为Nπ;第二行为M(M <= 20),表示蛋糕的层数为M。

输出

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

思路

一开始什么思路都没有,然后就手玩了一下样例。样例玩了很久才出来,然后发现玩样例的过程就是个搜索的过程。

所以这道题就可以用爆搜去做,爆搜不难写,但剪枝就没那么容易。首先可以预处理出剩下i层最小的蛋糕体积,储存为minv[i]。如果搜索剩下了i层,但剩余的体积小于minv[i]时,就可以剪去这枝。然后,如果剩余体积/最大半径* 2(即为最大侧面积)大于等于已知的最小侧面积时,也可以剪去这枝。

加上这两个以后,就可以从原来TLE8个点变为0ms了。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define MAXN 20005
#define INF 0x3f3f3f3f
using namespace std;

int n, m, ans=INF, temp, minv[MAXN];

void dfs(int vol, int cnt, int num, int r, int h)
{
    if(cnt==0)
    {
        if(vol==0) ans=min(ans, num);
        return;
    }
    if(2*vol/r+num>=ans || vol<minv[cnt]) return;
    for(int i=r; i>=cnt; i--)
    {
        if(cnt==m) num=i*i;
        temp=min(h, (vol-minv[cnt-1])/(i*i));
        for(int j=temp; j>=cnt; j--) dfs(vol-i*i*j, cnt-1, num+2*i*j, i-1, j-1);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++) minv[i]=minv[i-1]+i*i*i;
    dfs(n, m, 0, n, sqrt((double)n));
    if(ans==INF) printf("0\n");
    else printf("%d\n", ans);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注