| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:这题暴搜会超时,剪枝还得减细致一点In Reply To:这题暴搜会超时,剪枝还得减细致一点 Posted by:110120_119 at 2019-03-27 17:29:24 > /*
>
> 104K 63MS
> */
> #include<cstdio>
> #include<cmath>
> #pragma warning (disable:4996)
> using namespace std;
>
> int N, M; // N表示体积,M表示层数
> int minV[25], minA[25]; // minV[i]表示从最上面一层到第i层最小的体积,minA[i]表示从最上面一层到第i层最小的侧面积
> int area; // 搭建蛋糕过程中,当前的总面积
> int minArea; // 最小的表面积
>
> int maxVFOR_RH(int m,int r, int h ) //第m层时,最大半径r,最大高度h
> {
> int maxv=0;
> for (int i = 0; i < m; i++) //从该层往上,每一层都按照最大的半径和高度计算,求出在第m层时,上面最大体积
> {
> maxv += (r - i)*(r - i)*(h - i);
> }
> return maxv;
> }
>
> void dfs(int _V, int _M, int maxR, int maxH)
> {
> if (_M == 0) // 若刚好搭建好,即剩余层数为0
> {
> if (_V == 0) // 体积刚好满足
> {
> minArea = area > minArea ? minArea : area; // 更新最小表面积
> }
> return;
> }
>
> if (maxVFOR_RH(_M, maxR, maxH) < _V) //剪枝,若从该层开始往上,所构建的最大蛋糕体积 小于 剩余蛋糕体积,则无法构建
> return;
>
> // 剪枝,若剩余体积小于0或者小于剩下构建所需的最小体积,或者最大半径、高度小于当前层数,则都不需要继续构建了
> if (_V < 0 || _V < minV[_M] || maxR < _M || maxH < _M)
> return;
>
> if (area + minA[_M] >= minArea) // 剪枝,若当前面积加上剩下蛋糕最小侧面积 大于 最小的表面积,这个方案不是最优
> return;
>
> for (int rr = maxR; rr >= _M; rr--) // 半径从最大的尝试,最小为当前层数
> {
> if (_M == M) // 若当前构建的层数是最底层(即第一次构建),则初始化area,使其等于底层的上表面积
> area = rr * rr;
> for (int hh = maxH; hh >= _M; hh--) // 双重循环,遍历每一层中每一个半径与高度的所有情况
> {
> area += 2 * rr * hh; // 当前面积需要加上侧面积
>
> //printf("_M = %d rr=%d hh=%d area=%d\n", _M, rr, hh,area);
>
> dfs(_V - rr * rr * hh, _M - 1, rr - 1, hh - 1);
>
> area -= 2 * rr * hh; //复原当前状态
> }
> }
>
> }
>
> int main()
> {
> //freopen("input.txt", "r", stdin);
> //freopen("output.txt", "w", stdout);
>
> while (scanf("%d %d", &N, &M) != EOF)
> {
> //蛋糕是从下往上构建的
> minArea = 1 << 30; //最小表面积初始化成很大的值
> minV[0] = 0, minA[0] = 0;
>
> for (int i = 1; i <= M; i++) //从顶往下,记录到达每一层时,最小的体积以及最小的侧面积
> {
> minV[i] = minV[i - 1] + i * i * i; //当层体积为 R*R*R == i*i*i
> minA[i] = minA[i - 1] + 2 * i * i; //侧面积等于 2*R*H == 2*i*i
> }
>
> if (minV[M] > N) //如果从顶到第M层所需的最小体积小于给的N,则不可能构成蛋糕
> {
> printf("0\n");
> }
> else
> {
> int maxR, maxH; //求出最底层的最大半径和最大高度
> maxH = (N - minV[M - 1]) / (M * M) + 1; //底层最大高度=(所有体积-上面最小体积)/(底面积) + 1;
> maxR = sqrt(((N - minV[M - 1])) * 1.0 / M) + 1;
>
> //printf("maxH=%d maxR=%d\n", maxH, maxR);
>
> area = 0; //当前总面积为0
> dfs(N, M, maxR, maxH); //剩余体积N 剩余层数M 当前最底层的最大半径和高度
>
> if (minArea == 1 << 30)
> printf("0\n");
> else
> printf("%d\n", minArea);
> }
>
> }
>
> return 0;
> }
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator