[LuoGu] P1731 生日蛋糕

(color{red}{mathcal{Description}})

7月17日是 (Mr.W) 的生日，(ACM-THU) 为此要制作一个体积为的 (M) 层生日蛋糕，每层都是一个圆柱体。设从下往上数第 (i) ((1 leq i leq M)) 层蛋糕是半径为 (R_i) , 高度为 (H_i) 的圆柱。当 (i<M) 时，要求 (R_i>R_{i+1}) 且 (H_i>H_{i+1}) 由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积 (Q) 最小。令 (Q = Spi) ,请编程对给出的 (N) 和 (M) ，找出蛋糕的制作方案（适当的 (R_i) 和 (H_i) 的值），使 (S) 最小。（除 (Q) 外，以上所有数据皆为正整数）

(color{red}{mathcal{Input Format}})

有两行，第一行为 (N) ，表示待制作的蛋糕的体积为 (Npi)；第二行为 (M)，表示蛋糕的层数为 (M)。

(color{red}{mathcal{Output Format}})

仅一行，是一个正整数 (S)（若无解则 (S=0)）。

(color{red}{mathcal{DataSize Agreement}})

(1 leq N leq 20000 , 1 leq M leq 15).

(color{red}{mathcal{Hint}})

圆柱相关公式：(V=pi R^2H)体积 ；侧面积 (S'=2 pi RH)；底面积 (S=pi R^2) 。

(color{red}{mathcal{Solution}})

首先不难想到的是搜索，但直接搜索会很慢，考虑到要加一些剪枝：

可行性剪枝：当前体积加上下一层最小的体积也比 (n) 大，不可行；

最优性剪枝：
１、当前面积加上下一层的最小侧面积比记录的 (ans) 大，那么该种方案定然不是最优的；
２、如果剩余体积对应的下一层侧面积加上当前面积大于等于 (ans) ，该方案不是最优的（必须是大于等于因为下一层的半径取不到当前的 (r) ）

一个小技巧是预处理出每一层的最小体积以及最小面积

(color{red}{mathcal{Code}})

#include <bits/stdc++.h>
#define LL long long
#define reg register

using namespace std;

const int kMax = 21;
const int inf = 0x7f7f7f7f;

int mins[kMax], minv[kMax];
int N, M, Ans = inf;

void dfs(int v, int s, int p, int r, int h) {
  if (p == 0) {
  	if (v == N) Ans = min(Ans, s);
	return ;
  }
  if (v + minv[p - 1] > N) return ; // 可行性剪枝 
  if (s + mins[p - 1] > Ans) return ;  // 最优性剪枝
  if (s + (N - v) / r * 2 >= Ans) return ; //最优性剪枝
  for (reg int i = r - 1; i >= p; --i) {
  	if (p == M) s = i * i;
  	int minh = min(h - 1, (N - v - minv[p - 1]) / (i * i));
  	for (reg int j = minh; j >= p; --j)
  	  dfs(v + i * i * j, s + 2 * i * j, p - 1, i, j);
  }
}

int main() {
  scanf("%d%d", &N, &M);
  for (reg int i = 1; i <= 20; ++i) mins[i] = mins[i - 1] + i * i, minv[i] = minv[i - 1] + i * i * i;
  dfs(0, 0, M, N + 1, N + 1);
  printf("%d
", (Ans == inf ? 0 : Ans));
  
  return 0;
}

(color{red}{mathcal{Source}})

(NOI 1999)