AcWing 168. 生日蛋糕
原题链接
中等
作者:
十六
,
2021-01-23 17:32:00
,
所有人可见
,
阅读 474
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f, N = 20+5;
int n, m, ans;
int minv[N], mins[N]; //从上到小,前 k 层的最小体积和最小侧面积
int r[N], h[N]; //每一层的r 和 h
void dfs(int k, int v, int s){
//当前的体积加上剩余上面几层的最小体积大于需要的体积
if(v+minv[k] > n) return ;
//当前已有的面积已经大于找到过的最小面积
if(s+mins[k] >= ans) return ;
//根据前 k 层的体积和前 k 层的表面积的公式,可以推出下面的不等式
//(前k层的表面积) > (2/r[k+1])*(n-v)
//所以当 s + (2/r[k+1])*(n-v) >= ans 时,就没必要再搜索了
if(s+2*(n-v)/r[k+1] >= ans) return ;
if(k==0){
if(v==n) ans = s;
return ;
}
// r*r*h r 占的比重较大,所以先枚举 r 再枚举 h
for(int i=min(r[k+1]-1, (int)sqrt(n-v)); i>=k; i--){
for(int j=min(h[k+1]-1, (n-v)/(i*i)); j>=k; j--){
int t = 0;
if(k==m) t = i*i; //上表面
r[k] = i, h[k] =j;
dfs(k-1, v+i*i*j, s+2*i*j+t);
}
}
}
int main(){
scanf("%d%d", &n, &m);
for(int i=1; i<=m; i++){
minv[i] = minv[i-1] + i*i*i; //r*r*h
mins[i] = mins[i-1] + 2*i*i; //r*h
}
r[m+1] = h[m+1] = inf;
ans = inf;
dfs(m, 0, 0);
if(ans==inf) puts("0");
else cout<< ans<< endl;
return 0;
}