poj 1190 生日蛋糕（深搜+剪枝技巧）

poj 1190 生日蛋糕（深搜+剪枝技巧）

poj 1190 生日蛋糕（深搜+剪枝技巧）
总时间限制: 5000ms 内存限制: 65536kB

描述
7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。
设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时，要求Ri > Ri+1且Hi > Hi+1。
由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。
令Q = Sπ
请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。
（除Q外，以上所有数据皆为正整数）

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

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

样例输入
100
2

样例输出
68

提示
圆柱公式
体积V = πR2H
侧面积A’ = 2πRH
底面积A = πR2

来源
Noi 99

题意非常清晰，就是要求一个约束下另一个式子的最值，涉及数学公式部分较简单。
关键是怎么搜，一个想法是从下到上，另一个是从下到上，还有可能可以伴随着记忆化搜索。
搜索函数框架为dfs(int n,int m,int max/min r,int max/min h,int now_sum_rh)。
先看看要怎么剪枝，剪枝分为2个技巧：
1.考虑余下的子问题中r，h都取某最值如果体积都达不到要求的体积n，那么可以剪枝。
2.充分利用已经算出来的最小值，如果接下来子问题r，h都取某最值算出来的还要比min大，那么可以剪枝。
另外，会发现当从下往上搜索1.2中有很多重复的值可以利用，可以预处理，而从上往下搜索就很难办。故应该使用如此预处理+剪枝，从下往上搜，虽然未剪枝剪得尽善尽美，但是可以过了。

后来又做到了这个题目，写了一个剪枝没有尽善尽美的算法，却要2000ms+，虽然也能AC，但是与第一遍学习以后做的代码（见下面贴的代码）差距还是很大的，我想了想这个将近20倍的差距从哪儿来。
仔细一看，发现下面用到了一个隐性剪枝，搜索时候按r，h从大往小搜索，可以尽快得到可行解方便剪枝，因为从最小r，h搜索初期无效解太多（之前理论上有解实际上无解，加上整除问题注定要留有余地，所以无效很多），所以这么一个顺序之差有很大时间差距。说明第一遍学习时候没有看出来一个暗含的剪枝，即r，h从大往小搜索。
经典题目不厌百回做，就算很熟悉的题目或者学过的题目学会了忘了以后独立思考做一做还是可以发现新东西加深理解的。（6.5注）

Accepted    256kB   110ms   955 B   G++ 

#include<stdio.h>
#include<math.h>int n,m,min=0x1FFFFFFF,minV[21],minS[21],maxV;void dfs(int n,int m,int max_r,int max_h,int sum_rh,int R)
{if (m==1){if (max_r*max_r*max_h<n)return;for (int r=max_r;r*r>=n/max_h && r>=1;r--)if (n%(r*r)==0)if (2*(sum_rh+n/r)+R*R<min)min=2*(sum_rh+n/r)+R*R;return;}for (int r=max_r;r>=m;r--)for (int h=max_h;h>=m;h--){maxV=0;for (int i=1;i<m;i++)maxV+=(r-i)*(r-i)*(h-i);if (n-r*r*h<minV[m-1] || maxV<n-r*r*h) continue;if (R*R+2*(sum_rh+r*h+minS[m-1])>=min)continue;dfs(n-r*r*h,m-1,r-1,h-1,sum_rh+r*h,R);}return;
}int main()
{scanf("%d%dn",&n,&m);minV[0]=0;minS[0]=0;for (int i=1;i<=20;i++)minV[i]=minV[i-1]+i*i*i;for (int i=1;i<=20;i++)minS[i]=minS[i-1]+i*i;for (int R=floor(sqrt(n)+1e-5);R>=m;R--)dfs(n,m,R,n/R,0,R);printf("%dn",min!=0x1FFFFFFF?min:0);return 0;
}
//s=r1^2+2*(r1*h1+r2*h2+...+rn*hn),r,h递降