当前位置: 代码迷 >> 综合 >> noi99 生日蛋糕 搜索
  详细解决方案

noi99 生日蛋糕 搜索

热度:87   发布时间:2023-12-06 08:49:57.0

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

68

Hint

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

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;
}