网站建设按年收费吗,公司做一个网站如何定位,vpn网站模板,百度竞价排名展示方式题目链接
点此快速前往
题目总分析
就和我说的一样#xff0c;这道题就是DFS加剪枝#xff0c;非常好的一道题
我起初看到这个题我根本不知道怎么dfs才是正确的#xff0c; 感觉变量有这么多不确定的#xff0c;每一层的半径#xff0c;每一层的高度#xff0c;而且这…题目链接
点此快速前往
题目总分析
就和我说的一样这道题就是DFS加剪枝非常好的一道题
我起初看到这个题我根本不知道怎么dfs才是正确的 感觉变量有这么多不确定的每一层的半径每一层的高度而且这之间的联系在刚看到这个题的我看来十分的小应该是我太菜了导致的
深入往下看你就发现实际上这道题已经告诉了你每一层的限制了并不是完全无从下手至少你知道这一层的半径和高度一定小于等于它底下那一层的半径和高度-1所以我们不难想象出dfs的做法最下面那一层的半径最大值是假设只有一层n-1就是它起初的最大值那么最小值就是总共的层数因为每一层都要至少要少1所以最大的那一层半径和高度肯定就最小值就是层数
为什么不遍历高度而是半径呢
你稍微列一下式子你就会发现实际上半径对总面积的影响程度要高于高度的所以想要最小一定是从半径入手。 总体积 n ∑ i 1 m R i ∗ H i 总体积 n \sum_{i 1}^{m} R_i * H_i 总体积ni1∑mRi∗Hi 总面积 m R 0 2 ∑ i 1 m R i 2 ∗ H i 总面积 m R_0^2 \sum_{i1}^{m} R_i^2 * H_i 总面积mR02i1∑mRi2∗Hi
为什么总面积前面有个 R 0 2 R_0^2 R02
简单想想虽然是每个圆柱都被另一个比它小的圆柱盖住了一个圆的面积但是你从这个蛋糕的最上面去看就不难发现最上面的面积和其实就是最底层圆柱的顶面面积。
看到这可能已经想要去写了不过先停一下 这道题dfs搜索只是第一步而更重要的是剪枝由于处理数据的量也是非常大的如果不进行一些优化就没办法顺利进行
首先既然我们知道每一层最小的半径和高那么我们就不难算出来到每一层为止最小的体积和最小的面积分别是多少
有了上述的信息之后我们在准备遍历之前可以先判断一下
如果此时此刻接下来几层的最小面积加上此时的面积已经大于等于当前的最优解你那就没有必要去遍历了。同样接下里几层的最小体积加上此时的体积已经大于要求的总体积n那么也没必要去遍历了这个是比较难想的我们是从最下层遍历到最上层的也就是说假设此时此刻遍历的层数半径为r包括这一层之前的总体积为v以及总面积是s 总共的蛋糕体积是n那么如果 2 ∗ ( n − v ) / r 此时的最优解 2 * (n - v) / r 此时的最优解 2∗(n−v)/r此时的最优解同样也没有遍历下去的必要了
前两个好理解,第三个是什么东西啊 很好我开始看到的时候也非常困惑接下来推导一下你就懂了
从m开始now是已经搭建好的层数了now-1就是接下来之后的层 接下里的面积应该是 ∑ i 1 n o w − 1 R i 2 ∗ H i 接下里的面积应该是\sum_{i 1}^{now - 1} R_i^2 * H_i 接下里的面积应该是i1∑now−1Ri2∗Hi 看一下我第三条公式你可以清楚的发现 R i R_i Ri全部都小于当前这一层的 r 所以接下里的面积必然比 2 ∗ ( n − v ) / r 2 * (n - v) / r 2∗(n−v)/r大如果这个面积都大于等于最优解了那么就不需要遍历了
接下来就是代码实现了基本思路已经写完代码中有不理解的部分可以评论区提问一下或者私信。
总代码
#includebits/stdc.h
using namespace std;
const int N 25 , INF 0x3f3f3f3f;
int n,m;
int ans INF;
int Mins[N] , Minv[N];
void dfs(int now,int r,int h,int s,int v)
{int MH h;if(now 0){if(v n){ans min(ans, s);}return ;}if(Mins[now-1] s ans) return;if(Minv[now-1] v n) return;if(2 * (n - v) / r s ans) return;for(int ir-1;inow;i--){if(now m) s i * i;MH min(h-1 , (n - Minv[now-1] - v) / i / i);for(int j MH ; j now ; j--){dfs(now-1 , i , j , s 2 * i * j , v i * i * j);}}
}int main()
{cin n m;for(int i1;im;i){Mins[i] Mins[i-1] i * i * 2;Minv[i] Minv[i-1] i * i * i;}dfs(m,n,n,0,0);if(ans INF) cout 0 \n;else cout ans \n;return 0;
}
