题目链接：https://www.luogu.org/problem/P1731
思路：
一道非常棒的搜索剪枝题。
考虑从底向上进行搜索，在一个区间内枚举$r,h$。
考虑优化：
1.区间范围的优化
体积的公式是由$r,h$共同确定的，记录之前每一层的$r$，从之前的$r-1$开始枚举$r$。
对于$h$，根据公式，设剩余体积为$v_r$，可以把$min(v_r/(r *r),hlast-1)$作为上界。
2.搜索顺序优化
使用倒序搜索或许可以对搜索时间起到优化。
3.可行性、最优性剪枝
不难发现，当$1,2,3,...m$层的$h,r$皆为$1,2,3,...m$时，所得到的$v,s$最小。
可以选择预处理出前$i$层的最小$v,s$，与目前已经搜到的结果、最大体积$n$进行比较，进行剪枝。
还有一个比较难想的剪枝，在这里不想打$Latex$了，引用一位网上dalao的博客吧
代码：
#include <bits/stdc++.h> const int INF = 1 << 30; const int MAXM = 50; using namespace std; int n, m, ans = INF, r[MAXM], h[MAXM], vmin[MAXM], smin[MAXM]; void dfs(int dep, int vnow, int s1, int s2, int s3) { if(s3 < 0 || dep < 0) return ; if(s2 > ans) return ; if(dep == 0) { if(s3 == 0) ans = min(ans, s1 + s2); return ; } if(s1 + s2 + smin[dep] > ans) return ; if(vnow + vmin[dep] > n) return ; for(int i = r[dep + 1] - 1; i >= dep; i--) { if(dep == m) s1 = i * i; int jj = min(s3 / (i * i), h[dep + 1] - 1); for(int j = jj; j >= dep; j--) { if(s1 + s2 + ((n - vnow) * 2 / i) > ans) continue; r[dep] = i; h[dep] = j; dfs(dep - 1, vnow + i * i * j, s1, s2 + 2 * i * j, s3 - (i * i * j)); r[dep] = 0; h[dep] = 0; } } } int main() { cin >> n >> m; for(int i = 1; i <= m; i++) { vmin[i] = vmin[i - 1] + i * i * i; smin[i] = smin[i - 1] + 2 * i * i; } r[m + 1] = h[m + 1] = sqrt(n); dfs(m, 0, 0, 0, n); ans == INF ? (cout << "0" << endl) : (cout << ans << endl); return 0; }