【洛谷】【搜索+剪枝】P1731 [NOI1999]生日蛋糕

时间:2024-07-05 18:34:20

【题目背景:】

7月17日是Mr.W的生日,ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕,每层都是一个圆柱体。

【题目描述:】

设从下往上数第i(1<=i<=M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i<M时,要求 \(R_i > R_{i+1}\) 且 $H_i>H_{i+1}H $。

由于要在蛋糕上抹奶油,为尽可能节约经费,我们希望蛋糕外表面(最下一层的下底面除外)的面积Q最小。

令Q= Sπ

请编程对给出的N和M,找出蛋糕的制作方案(适当的Ri和Hi的值),使S最小。

(除Q外,以上所有数据皆为正整数)

【输入格式:】

有两行,第一行为N(N<=20000),表示待制作的蛋糕的体积为Nπ;第二行为M(M<=15),表示蛋糕的层数为M。

【输出格式:】

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




[算法分析:]

就是搜索啊搜索啊搜索,但是要剪枝啊剪枝啊剪枝啊

像我这么弱连这道题的搜索都要调试的人应该是没有几个了..

观察一个蛋糕的俯视图,上表面的面积其实就是最下面那一层的底面积,所以在第一次搜索的时候加入这个底面积,之后就只用考虑侧面积就好啦.

就是每次枚举r和h,如何选取上下界呢?

将上一层的高度记作lh,上一层的半径记作lr,则上界很好判断,就是\(lh-1\)和\(lr-1\),

底层应该是选取\(\sqrt[3]{20000}\)约为28的范围

现在考虑下界:

自然选取1是会T得很惨的,下界就是最小值嘛,最上面一层的\(r\)和\(h\)的最小值都是\(1\)啊,那还有几层下界就是几啦!

然后来愉快地剪枝:

比较好想的剪枝是这两个:

  1. 当当前的面积总和已经超过之前的答案时,\(return\)

  2. 当当前体积超过了要求的体积时,\(return\)

还有一些剪枝,思维难度也不算高:

  • 当现在的已有体积加上之后的最大(并不是真正的最大,会比最大还要大一些)体还要小于要求的体积时,\(return\)

  • 当当前的已有面积加上之后的最小(自然也是比真正的最小还要小一些)面积比已有答案还要大时,\(return\)

关于搜索顺序的选择:

这个东西..就是一个玄学...一共有\(A_2^2\ A_2^2\)种选择自己试试就好啦(雾




\([Code:]\)

#include<iostream>
#include<cstdio>
#define re register
using namespace std; int ans = 2e9;
int n, m; void dfs(int t, int s, int v, int lr, int lh) {
if(s >= ans) return;
if(t == m+1 && v == n) {
ans = min(ans, s);
return;
}
if(v >= n) return;
int k = m - t + 1;
if(k * lr * lr * lh + v < n) return;
if(k * 2 + s > ans) return;
if(t == 1) {
for(re int r=lr; r>=m; --r) {
for(re int h=m; h<=lh; ++h) {
dfs(t + 1, s + r * r + 2 * r * h, v + r * r * h, r, h);
}
}
}
else for(re int r=lr-1; r>=m-t+1; --r) {
for(re int h=m-t+1; h<lh; ++h) {
dfs(t + 1, s + 2 * r * h, v + r * r * h, r, h);
}
}
} int main() {
scanf("%d%d", &n, &m);
dfs(1, 0, 0, 28, 28);
if(ans == 2e9) puts("0");
else printf("%d\n", ans);
}