| ||||||||||
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 |
这题暴搜会超时,剪枝还得减细致一点/* 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