AcWing168 生日蛋糕(剪枝)

原题链接

思路的话，就是暴搜加剪枝，中间有个放缩

思路看这篇

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int) (x).size()
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> VI;
typedef double db;

const int N = 25;
int n, m, minv[N], mins[N], ans = 0x3f3f3f3f; // 预处理每层最小体积和最小面积
int H[N], R[N];
void dfs(int u, int s, int v) {  
  if (s+mins[u-1] >= ans) return;
  if (s+2*(n-v)/R[u+1] >= ans) return;
  if (v+minv[u-1] > n) return; 
  if (u == 0) {
    if (v == n) ans = s;
    return;
  }
  for (int r = min(R[u+1]-1, (int) sqrt(n-v-minv[u-1])); r >= u; r--) {
    for (int h = min(H[u+1]-1, (n-v-minv[u-1])/r/r); h >= u; h--) {
      int th = H[u], tr = R[u];
      H[u] = h;
      R[u] = r;
      int t = 0;
      if (u == m) t = r*r;
      dfs(u-1, s+2*r*h+t, v+r*r*h);
      H[u] = th, R[u] = tr;
    }
  }
}
void solve() {
  cin >> n >> m;
  // 题目说了所有数皆为正整数，因此第i层高大于等于i,底面半径大于等于i
  for (int i = 1; i <= m; i++) { 
    mins[i] = mins[i-1]+2*i*i;
    minv[i] = minv[i-1]+i*i*i;
  }
  R[m+1] = H[m+1] = 0x3f3f3f3f; 
  dfs(m, 0, 0);
  if (ans == 0x3f3f3f3f) ans = 0;
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();
  return 0;
}