[NOI1999]生日蛋糕

题目背景

7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层

生日蛋糕，每层都是一个圆柱体。

设从下往上数第i(1<=i<=M)层蛋糕是半径为\(R_i\), 高度为\(H_i\)的圆柱。当i<M时，要求 \(R_i>R_{i+1}\) 且 \(H_i>H_{i+1}\) 。

由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。

令Q= Sπ

请编程对给出的N和M，找出蛋糕的制作方案（适当的\(R_i\)和\(H_i\)的值），使S最小。

（除Q外，以上所有数据皆为正整数）

题目描述

输入输出格式

输入格式：

有两行，第一行为N（N<=20000），表示待制作的蛋糕的体积为Nπ；第二行为M(M<=15)，表示蛋糕的层数为M。

输出格式：

仅一行，是一个正整数S（若无解则S=0）。

输入输出样例

输入样例#1：

100

2

输出样例#1：

68

搜索的剪枝是真的恶心。

似乎我的代码还没有剪掉全部，太恶心没话说。

1.当前值不能更新答案，return。

2.当前值加上剩下体积能构成的最小表面积>ans，return。

3.枚举的蛋糕大小比剩余的体积大，break。

4.若选用当前蛋糕，剩余体积小于上方蛋糕的最小体积（预处理），break。

具体见代码

#include<bits/stdc++.h>

using namespace std;

int n,m,inf=2000000000,ans,sum,canvv[20010];

void dfs(int k,int lasth,int lastr,int canv)

{

    if(sum>=ans)return;if(sum+2*canv/lastr>ans)return;//1 2

    if(k==m+1)

    {

        if(canv)return;ans=min(ans,sum);return;

    }

    for(int h=m-k+1;h<min(canv+1,lasth);h++)

        for(int r=m-k+1;r<min(canv+1,lastr);r++)

        {

            if(h*r*r>canv)break;if(canv-h*r*r<canvv[k+1])break;//3 4

            if(k==1) sum+=r*r;

            sum+=2*r*h;

            dfs(k+1,h,r,canv-h*r*r);

            sum-=2*r*h;

            if(k==1) sum-=r*r;

        }

}

int main()

{

    scanf("%d%d",&n,&m);ans=inf;

    for(int i=m;i>=1;i--)

    canvv[i]=canvv[i+1]+(m-i+1)*(m-i+1)*(m-i+1);

    dfs(1,inf,inf,n);if(ans==inf)ans=0;cout<<ans<<endl;

}