noi99 生日蛋糕搜索_综合

Description

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外，以上所有数据皆为正整数）

Input

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

Output

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

Sample Input

100
2

Sample Output

Hint

圆柱公式
体积V = πR ²H
侧面积A' = 2πRH
底面积A = πR ²

Source

Noi 99

思路：

搜索，枚举蛋糕每一层的r和h。

剪枝:

1、2*(n-v)/far+s>=S 时，可以直接减去。

2、做两个表mins[i]、minv[i]，分别代表从下向上数第i层时，第i层的上面的最小体积和表面积。

for(int i=m; i>=1; i--) {minv[i]=minv[i+1]+(m-i+1)*(m-i+1)*(m-i+1);mins[i]=mins[i+1]+2*(m-i+1)*(m-i+1);
}

如果s+mins[x]>=minS或v+minv[x]>n都可以剪掉

代码：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;int n,m;int minv[35]= {0},mins[35]= {0};
void make() {minv[m+1]=mins[m+1]=0;for(int i=m; i>=1; i--) {minv[i]=minv[i+1]+(m-i+1)*(m-i+1)*(m-i+1);mins[i]=mins[i+1]+2*(m-i+1)*(m-i+1);}
}int minS=(1<<30);
void dfs(int x,int s,int v,int far,int fah) {if(s+mins[x]>=minS||v+minv[x]>n||2*(n-v)/far+s>=minS) {return ;}if(x==m+1) {if(s<minS&&v==n) {minS=s;}return ;}for(int i=far-1; i>=m-x+1; i--) {int s1=s;if(x==1) {s1+=i*i;}for(int j=min(fah-1,n/i/i); j>=m-x+1; j--) {int v1=v;v1+=i*i*j;s1+=2*i*j;dfs(x+1,s1,v1,i,j);s1-=2*i*j;}}return ;
}int main() {scanf("%d%d",&n,&m);make();float x=n;dfs(1,0,0,(int)sqrt(x)+2,n/m/m+1);if(minS!=(1<<30))printf("%d",minS);else{printf("0");}return 0;
}

noi99 生日蛋糕 搜索

noi99 生日蛋糕搜索