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