AcWing 168. 生日蛋糕（搜索）

AcWing 168. 生日蛋糕（搜索）

深度优先搜索 + 剪枝

原题链接

感悟：本题的小细节还挺多的，也正是利用这些题目给的小细节来增加剪枝条件的。这个题是我第一次遇到需要一些数学式子推到的题目，尽管不难，但第一次碰到也很蒙，虽然数学的学习还算可以，但应用到一些实际东西上还是无从下手，得加强加强。

NOTE

本题都带有pai，且题目最后不用输出，则一起全部舍去

题目思路

• 搜索对象及顺序： 深度搜，肯定是对层数下手的，然后从下往上
• 枚举对象及优化： 枚举r,h先r因为影响因子更大（v = r * r * h）
• dfs 参数：void dfs(int u, int v, int s); //u当前深度，v当前体积，s当前面积

剪枝优化

• 当前层的R,H的范围–与剩余体积，当前深度有关 （可行性）
  – dep <= R <= min{ sqrt(n-v) , R[dep + 1] - 1 }
  – dep <= H <= min{ (n-v)/r*r , H[dep + 1] - 1 }
• 到达当前层的根据s,v看是否需要继续 （可行性，最优性）
  – minv[dep] + v > n(总体积)
  – mins[dep] + s >= ans(当前最优解)
• 当前的s,v之间的关系 （可行性）
  – s + 2*(n-v)/R[dep+1] >= ans 这个是最难想的，推导还变了型

证明

（到时候补一张图，确实有点麻烦）

ACcode

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;const int N = 25, INF = 1e9;//这种无穷挺好啊int n, m;
int minv[N], mins[N]; //存放每层最小r，h
int R[N], H[N];       //存放枚举中使用的r，h，最后只会剩下一组最优解
int ans = INF;void dfs(int u, int v, int s)
{//剪枝（可行性）：当前层体积的极限关系if(minv[u] + v > n) return;    //剪枝（最优性）：当前层面积与已知最优的关系if(mins[u] + s >= ans) return;//剪枝（可行性）：当前体积与面积之间的关系if(s + 2*(n-v)/R[u+1] >= ans) return;//返回条件if(!u){if(v == n) ans = s;return;}//枚举顺序：1.从大到小 2.先r后hfor(int r = min((int)sqrt(n-v), R[u+1] - 1); r >= u; r--)for(int h = min((n-v)/(r*r), H[u+1] - 1); 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);cout << ans << endl;return 0;
}