Acwing168.生日蛋糕

Acwing 算法提高课 剪枝

T4 生日蛋糕

原题(Acwing168.生日蛋糕)

搜索思路 外部搜索：

$$\text{枚举每一层蛋糕} \rightarrow \text{枚举半径和高度} \rightarrow \text{递归,若搜到M+1层则更新最优值并回溯}$$

那么我们该如何剪枝呢？

I. 优化搜索顺序

1. 从上向下枚举,下面体积大留给上面的体积较小,分支较少

2. 内部枚举时先枚举半径再枚举体积,对于表面积和体积的影响,半径是二次级别的,影响更大,分支更小

3. 枚举高度和半径时从大到小枚举

II. 可行性剪枝(计算一下我们半径和高度的枚举范围,数学推导警告)

我们自上而下标记各蛋糕层为1,2,3...M,我们现在讨论第u层的半径高度范围

对于半径(R)而言

$$R_{u} \ge u(\text{上面有u-1层,每层半径为1时取到当前层半径最小})$$ $$R_{u} \le R_{u + 1} - 1$$

对于高度(H)而言

$$u \le H_{u} \le H_{u + 1} - 1$$ $$\because\text{ 先枚举半径}\therefore\text{半径此时已知,若已用体积为V则有}H_{u} \le \frac{N-V}{R_{u}^2}$$

综上，有

III. 另外的可行性剪枝

我们可以先预处理出来前u层的最小体积和最小侧表面积
记作$V_{minu}$和$S_{minu}$

$$\text{那么当}V_{minu} + V > N\text{时},可以直接回溯$$

IV. 最优性剪枝

$$\text{若}S_{minu}+S >= ans\text{时可直接回溯}$$

V. 数学推导来寻找关系(最困难的一个剪枝)

对于未填充的几层蛋糕,有

$$\text{也就是说当}S+S_{侧} > S + \frac{2}{R_{u+1}} (N - V) \ge ans \text{时可直接回溯}$$

//2.10 19:26 WA : 忘记从大到小枚举半径了
//2.10 19:27 AC

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e4 + 10, M = 30;

int n, m, ans;
int ve[M], se[M], R[M], H[M];

void dfs(int u, int V, int S){
    if(V + ve[u] > n) return;
    if(ans != 0 && S + se[u] >= ans) return;
    if(ans != 0 && S + 2 * (n - V) / R[u + 1] >= ans) return;
    if(u == 0){
        if(V == n)ans = S;
        return;
    }
    
    for(int r = R[u + 1] - 1; r >= u; r --){
        for(int h = min((n - V) / (r * r), H[u + 1] - 1); h >= u; h --){
            R[u] = r;
            H[u] = h;
            if(u == m) dfs(u - 1, r * r * h, r * r + 2 * r * h);
            else dfs(u - 1, V + r * r * h, S + 2 * r * h);
        }
    }
}

int main(){
    freopen("HAPPYBirthDay.in", "r", stdin);
    freopen("HAPPYBirthDay.out", "w", stdout);
    
    scanf("%d%d", &n, &m);
    //init
    for(int i = 1; i <= m; i ++){
        se[i] = se[i - 1] + 2 * i * i;
        ve[i] = ve[i - 1] + i * i * i;
    }
    
    R[m + 1] = H[m + 1] = n;
    
    dfs(m, 0, 0);
    
    cout << ans << endl;
    return 0;
}