洛谷P1731 生日蛋糕 做题记录
题意简述
一个生日蛋糕由几个圆柱体组成，每个圆柱体的底面半径和高从下到上严格递减，现给出蛋糕的体积 N pi 以及层数 M，试求蛋糕的最小表面积。
思路速通
基本为 DFS ，对于每层的半径以及高度进行枚举，然后增加一些剪枝。
以下为较为重要的剪枝：
- 体积明显不够剩下的层数进行分配时 return；
- 当前体积已经>n时return；
- 当前已经累加出的表面积明显大于当前已经算出的最小总表面积时 return；
- 当前已经累加出的表面积与剩下部分最小的表面积之和明显打与当前已经算出的最小总表面积时 return ；
代码实现
#include<bits/stdc++.h>
#define bot r[1]*r[1]
using namespace std;
const int inf=2147483647;
int n,m;
int r[25],h[25];
int minn=inf;void dfs(int now,int v_last,int s,int last_m){if(last_m<0){return ;}if(v_last<0){return ;}//体积>n时剪枝if(s>=minn){return ;}if(v_last==0&&!last_m){s+=bot;minn=min(minn,s);return ;}if(s+last_m*2+bot>minn){return ;}//当前表面积与剩余最小表面积相加之和大于当前已经算出的最小总表面积时剪枝if(v_last>r[now-1]*r[now-1]*h[now-1]*last_m){return ;}//当前剩余体积不够剩余的最大体积分配时剪枝for(int i=r[now-1]-1;i>=last_m;i--){//枚举半径for(int j=h[now-1]-1;j>=last_m;j--){//枚举高度if(v_last>=i*i*j&&now+1<=m+1){r[now]=i;h[now]=j;dfs(now+1,v_last-i*i*j,s+2*i*j,last_m-1);r[now]=0;h[now]=0;}}}return ;
}int main() {scanf("%d %d",&n,&m);if(m==1){//只有一层时特判//朴素暴力for(int i=n;i>=1;i--){for(int j=n;j>=1;j--){if(i*i*j==n){minn=min(minn,2*i*j+i*i);}}}printf("%d",(minn==inf?0:minn));return 0;}r[0]=(int)sqrt(n);h[0]=(int)sqrt(n);dfs(1,n,0,m);printf("%d",(minn==inf?0:minn));//最终还要判断是否有方案return 0;
}