[dfs] aw168. 生日蛋糕(dfs剪枝與優化+分類讨論+思維+公式推導+數學+好題)

文章目錄

• • 1. 題目來源
  • 2. 題目解析

1. 題目來源

連結：168. 生日蛋糕

2. 題目解析

非常非常經典的題目，優化很難…

首先的首先，了解題意，問題抽象。在總體積為

n

，總層數為

m

的情況下确定每層的

r

和

h

，使得要去的蛋糕外表面積最小。

首先确定枚舉順序，枚舉每層情況，再枚舉每層的

r

和

h

，保證

r

、

h

是遞增的整數。枚舉的種類是指數級别的，需要加入大量剪枝才可能通過本題。

優化：

• 優化搜尋順序：從底向上枚舉蛋糕每一層，因為底層占用體積大，後續分支少。每層中先枚舉

  r

  再枚舉

  h

  且也是從大到小枚舉，因為

  r

  是平方級别，變化快。
• 可行性剪枝與最優化剪枝：
  • 如果上一層半徑和高度确定，那麼對于本層來講，半徑最少是所在的層高，因為最小高度是 1，最大不能比下一層大。高度同樣如此。故高度和半徑都在枚舉時有範圍限制。
  • 如果前面所有層已經用了

    v

    體積和

    s

    表面積，那麼如果後面所有層即便按照最小半徑、高度配置設定也無法構成蛋糕或者更新最優解的話，也可以直接傳回。
  • 推導體積和表面積公式之間的聯系，這個是最難的，如果不加這個條件，在資料較強的情況下容易

    TLE

    。用體積估算前

    u

    層的最小表面積。

太難了。

具體剪枝推導，來自大佬：

自己的手寫筆記，比較亂：

時間複雜度： O ( 指 數 級 ) O(指數級) O(指數級)

空間複雜度： O ( n ) O(n) O(n)

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

using namespace std;

const int N = 25;

int n, m;
int minv[N], mins[N];
int R[N], H[N];
int res = 1e9;

// 自底向上，處理第 u 層，v 為之前的總體積，s 為之前的表面積
void dfs(int u, int v, int s) {
    if (v + minv[u] > n) return ;           // 可行性剪枝
    if (s + mins[u] >= res) return ;        // 最優性剪枝
    if (s + 2 * (n - v) / R[u + 1] >= res) return ;     // 體積和面積關系，剪枝

    if (!u) {                               // 搜完所有層
        if (v == n) res = s;                // 如果體積恰好等于 n，則此時的 s 一定可以更新 res
        return ;
    }

    // 先枚舉 r，再枚舉 h，且從大到小枚舉
    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;     // 第 u 層的半徑和高度确定
            dfs(u - 1, v + r * r * h, s + 2 * r * h + t);
        }
    
}

int main() {
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; i ++ ) {
        minv[i] += minv[i - 1] + i * i * i;         // r^2*h    r=h=1
        mins[i] += mins[i - 1] + 2 * i * i;         // 側面積
    }

    // 設定兩個哨兵，關于 r[u], h[u] 的範圍限制時，需要用到 r[u+1]，h[u+1] 來取 min，是以需要設定兩個哨兵
    R[m + 1] = H[m + 1] = 1e9;

    // 從 m 層開始，目前體積、表面積都是 0
    dfs(m, 0, 0);

    if (res == 1e9) res = 0;                        // 無解情況
    printf("%d\n", res);

    return 0;
}