《生日蛋糕》题解 id 7901

常规
1

dfs
从最下层开始
每次枚举半径和高度并记录
根据公式计算
体积V=R2H；侧面积S′=2RH；底面积S=R2 (π舍去)

    for (int i=1;i<=m;i++) {
        V[i]=V[i-1]+i*i*i;
        S[i]=S[i-1]+2*i*i;
    }//初始化 前缀最小的体积和面积
    R[m+1]=H[m+1]=0x3f3f3f3f;//第0层

void dfs(int step,int v,int s) {
    if(v+V[step]>n||s+S[step]>=ans||s+2*(n-v)/R[step+1]>=ans) 
		return;//剪枝 
    /*
        s+2*(n-v)/R[step+1]>=ans
        表示当前的面积s+剩下的最小侧面积不小于答案ans
        2*(n-v)/R[step+1]需要通过计算得到
        联立 体积和侧面积公式
        V=R**2H得H=V/(R**2)
        S′=2RH=2V/R
        (n-v)为剩下需要的体积
    */
    if(!step){
        if(n==v) ans=s;
        return;
    }
    for(int r=min((int)sqrt(n-v),R[step + 1]-1);r>=step;r--){
    //(int)sqrt(n-v) 为 剩下需要的体积除以高度1再开方 即当前情况下最大的半径
        for(int h=min((n-v)/r/r,H[step+1]-1);h>=step;h--) 
        //(n-v)/r/r 为 剩下需要的体积除以半径的平方 即高度
		{
            R[step]=r,H[step]=h;//记录
            dfs(step-1,v+r*r*h,s+2*r*h+(step==m)*r*r);//如果是最下层 面积还要加半径的平方
        }
    }
}
4 个赞