AcWing 168. 生日蛋糕
原题链接
中等
作者:
Anoxia_3
,
2021-05-16 13:05:43
,
所有人可见
,
阅读 263
/*
搜索顺序优化:自底向上搜、从大到小枚举R、H
u <= R[u] <= min(R[u+1] - 1 , sqrt(n-v))
u <= H[u] <= min(H[u + 1] - 1 , (n - v) / (r * r))
可行性剪枝:每一层的体积要不大于上限。先预处理一个minv[u]表示前u层的最小体积,如果当前层的体积+minv(u) > n 直接return
最优性剪枝:如果面积已经超过,直接return。先预处理一个mins[u]表示前u层的最小面积,只有s+mins(s) < ans才更新
最优性剪枝:
前u层体积之和(因为自底向上求,所以v表示自底到第u层的体积之和):n - v = ΣR[k]*R[k]*H[k]
前u层面积之和:S[u] = Σ2*R[k]*H[k] = 2/R[u+1] * ΣR[k]*H[k+1]*R[k+1] > 2/R[u+1] * ΣR[k]*R[k]*H[k] = 2/R[u+1] * (n - v)
总面积(同理s表示当前面积之和):s + S[u] > s + 2/R[u+1] * (n - v) ,当右边>=ans时跳过。
*/
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 25 , INF = 1e9;
int R[N] , H[N];
int minv[N] , mins[N];
int n , m;
int ans = INF;
void dfs(int u , int v , int s)
{
if(v + minv[u] > n) return;
if(s + mins[u] >= ans) return;
if(s + 2 * (n - v) / R[u + 1] >= ans) return;
if(!u)
{
if(v == n) ans = s;
return;
}
for(int r = min(R[u + 1] - 1 , (int)sqrt(n - v)) ; r >= u ; r--)
for(int h = min(H[u + 1] - 1 , (n - v) / (r * r)) ; h >= u ; h--)
{
int t = 0;
if(u == m) t = r * r;
R[u] = r , H[u] = h;
dfs(u - 1 , v + r * r * h , s + 2 * r * h + t);
}
}
int main()
{
cin >> n >> m;
for(int i = 1 ; i <= m ; i++)
{
minv[i] = minv[i - 1] + i * i * i;
mins[i] = mins[i - 1] + 2 * i * i;
}
R[m + 1] = H[m + 1] = INF;
dfs(m , 0 , 0);
if(ans == INF) cout << 0 << endl;
else cout << ans << endl;
return 0;
}