题目背景
7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层
生日蛋糕，每层都是一个圆柱体。
设从下往上数第i(1<=i<=M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i<M时，要求R_i>R_{i+1}Ri>Ri+1且H_i>H_{i+1}Hi>Hi+1。
由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。
令Q= Sπ
请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。
（除Q外，以上所有数据皆为正整数）
题目描述
输入输出格式
输入格式：
有两行，第一行为N（N<=20000），表示待制作的蛋糕的体积为Nπ；第二行为M(M<=15)，表示蛋糕的层数为M。
输出格式：
仅一行，是一个正整数S（若无解则S=0）。
输入输出样例
输入样例#1： 复制
100
2
输出样例#1： 复制
68
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,ans=0x7f7f7f7f;
int r[],h[];
int mins[],minv[];
void dfs(int r,int h,int deep,int s,int v){
if(s>ans) return ;//第一层剪枝
if(v==n&&deep>) return ;//第二层剪枝
if(v+minv[deep]>n) return ;
if(s+mins[deep]>ans) return ;
if(v==n&&deep==){
ans=min(ans,s);
return ;
}
for(int i=r;i>=deep;i--)
for(int j=h;j>=deep;j--){
if(deep==m) dfs(i-,j-,deep-,s+*i*j+i*i,v+j*i*i);
else dfs(i-,j-,deep-,s+*i*j,v+j*i*i);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
mins[i]=mins[i-]+i*i*;
minv[i]=minv[i-]+i*i*i;
}
dfs(sqrt(n),sqrt(n),m,,);
if(ans==0x7f7f7f7f) printf("");
else cout<<ans;
}
50分dfs
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,ans=0x7f7f7f7f;
int r[],h[];
int mins[],minv[];
void dfs(int r,int h,int deep,int s,int v){
if(s>ans) return ;//第一层剪枝
if(v==n&&deep>) return ;//第二层剪枝
if(v+minv[deep]>n) return ;
if(s+mins[deep]>ans) return ;
if(s+*(n-v)/(r+)>=ans) return ;
if(v==n&&deep==){
ans=min(ans,s);
return ;
}
if(deep==) return ;
for(int i=r;i>=deep;i--){
int yy=min((n-v-minv[deep-])/(i*i),h);
for(int j=yy;j>=deep;j--){
if(deep==m) dfs(i-,j-,deep-,s+*i*j+i*i,v+j*i*i);
else dfs(i-,j-,deep-,s+*i*j,v+j*i*i);
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
mins[i]=mins[i-]+i*i*;
minv[i]=minv[i-]+i*i*i;
}
dfs(sqrt(n),sqrt(n),m,,);
if(ans==0x7f7f7f7f) printf("");
else cout<<ans;
}
一通乱搞的剪枝