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(1<=M <= 20)，表示蛋糕的层数为M。

Output

仅一行，是一个正整数S（若无解则S = 0）。

Sample Input

100
2

100

Sample Output

68

Hint

圆柱公式
体积\(V = πR^2H\)
侧面积\(A' = 2πRH\)
底面积\(A = πR^2\)

题解

对于这种没有多项式复杂度的题目显然最好的做法是搜索。
但是这可是道NOI的题目，所以我们还要进行一些剪枝，我这里可能不是所有的剪枝都用了，但足够了，POJ16ms

首先我们搜索有5个状态，剩余层数，用了的表面积，用了的体积，当前层的高度，当前层的半径。

剪枝

上下界剪枝（范围剪枝）
我们在第dep层时，只需要在以下范围内枚举高度和半径即可：
\(R\in [dep,min(\lfloor \sqrt{N-v} \rfloor,r[dep+1]-1)]\)
\(H\in [dep,min(\lfloor \frac{N-v}{R^2} \rfloor,h[dep+1]-1)]\)
优化搜索顺序
上面的范围中，倒序枚举。
可行性剪枝/最优化剪枝（见注释）

代码

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,ans;
int mincake[30];

void dfs(int last,int s,int v,int h,int r){
    if(last==0){
        if(v==n&&s<ans){
            ans=s;
        }
        return;
    }
    if(v+mincake[last-1]>n)return;//当前体积+下一层最小体积>总体积，可行性剪枝
    if(2*(n-v)/r+s>=ans)return;//最优性剪枝
    for(int i=r-1;i>=last;i--){
        if(last==m)s=i*i;
        int hh=min((n-v-mincake[last-1])/(i*i),h-1);
        for(int j=hh;j>=last;j--){
            dfs(last-1,s+2*i*j,v+i*i*j,j,i);
        }
    }
}

int main(){
    cin>>n>>m;
    ans=1<<30;
    for(int i=1;i<=20;i++)mincake[i]=mincake[i-1]+i*i*i;//第i层最小的蛋糕体积
    dfs(m,0,0,n+1,n+1);
    if(ans==1<<30)cout<<0;
    else cout<<ans;
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

int n,m,ans;

int mincake[30];

void dfs(int last,int s,int v,int h,int r){

if(last==0){

if(v==n&&s<ans){

ans=s;

}

return;

}

if(v+mincake[last-1]>n)return;//当前体积+下一层最小体积>总体积，可行性剪枝

if(2*(n-v)/r+s>=ans)return;//最优性剪枝

for(int i=r-1;i>=last;i--){

if(last==m)s=i*i;

int hh=min((n-v-mincake[last-1])/(i*i),h-1);

for(int j=hh;j>=last;j--){

dfs(last-1,s+2*i*j,v+i*i*j,j,i);

}

int main(){

cin>>n>>m;

ans=1<<30;

for(int i=1;i<=20;i++)mincake[i]=mincake[i-1]+i*i*i;//第i层最小的蛋糕体积

dfs(m,0,0,n+1,n+1);

if(ans==1<<30)cout<<0;

else cout<<ans;

return 0;

}

发送评论编辑评论