P1731 [NOI1999]生日蛋糕

diggersun

https://www.luogu.org/problemnew/show/P1731

7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为N*pi的M层生日蛋糕，每层都是一个圆柱体。 设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时，要求Ri > Ri+1且Hi > Hi+1。 由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。 令Q = S*pi 请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。（除Q外，以上所有数据皆为正整数）
每组数据两行，第一行为N（N <= 10000），表示待制作的蛋糕的体积为N*pi；第二行为M(M <= 20)，表示蛋糕的层数为M。
输出仅一行，是一个正整数S（若无解则S=0）。
测试样例1
输入
100
2
输出
68

diggersun

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int n,m;
   
5. int res=99999999;
   
6. 
   
7. bool check(int dep,int r,int h,int v,int s)
   
8. {
   
9.     int maxv=0,mins=0,minv=0;
   
10.     for(int i=1; i<=dep; ++i)
    
11.     {
    
12.         maxv+=(r-i)*(r-i)*(h-i);
    
13.         mins+=2*i*i;
    
14.         minv+=i*i*i;
    
15.     }
    
16.     return ((v+minv<=n)&&(v+maxv>=n)&&(s+mins<=res));
    
17. }
    
18. 
    
19. void dfs(int dep,int r,int h,int v,int s)
    
20. {
    
21.     if(dep==0)
    
22.     {
    
23.         if(v==n) res=min(res,s);
    
24.     }
    
25.     else
    
26.     if( check(dep,r,h,v,s) )
    
27.         for(int nh=h-1; nh>=dep; --nh)
    
28.             for(int nr=r-1; nr>=dep; --nr)
    
29.                dfs(dep-1,nr,nh,v+nr*nr*nh,s+2*nr*nh);
    
30. }
    
31. 
    
32. int main()
    
33. {
    
34.     cin>>n>>m;
    
35.     for(int h=m; h<=n; h++)
    
36.         for(int r=m; h*r*r<=n; ++r)
    
37.             dfs(m-1,r,h,r*r*h,2*r*h+r*r);
    
38.     if(res==9999999) res=0;
    
39.     cout<<res;
    
40.     return 0;
    
41. }
    

复制代码

lyc

1. #include<iostream>
   
2. #include<cstdio>
   
3. #include<algorithm>
   
4. #include<cmath>
   
5. using namespace std;
   
6. int n,m;
   
7. int minv[25], mins[25];
   
8. bool flag = 0;///是否有答案
   
9. int ans=0x3f3f3f3f;
   
10. void dfs(int now, int s, int v, int lr, int lh){
    
11.     if(now == 0){
    
12.         if(v == n) {
    
13.             ans = min(ans, s);
    
14.             flag = 1;
    
15.         }
    
16.         return ;
    
17.     }
    
18.     if(s + mins[now] > ans || v + minv[now] > n || s + 2*(n - v)/lr > ans) return ;
    
19.     ///面积的最优性剪枝；体积的可行性剪枝；
    
20.     for(int r=lr-1; r>=now; r--){
    
21.         if(now == m) s = r*r;///俯视图圆的面积在第一次搜索时加上
    
22.         int uph = min((n-v-minv[now-1])/(r*r), lh - 1);
    
23.         for(int h=uph; h>=now; h--)
    
24.         {
    
25.             dfs(now - 1, s+2*r*h, v+r*r*h, r, h);
    
26.         }
    
27.     }
    
28. }
    
29. int main()
    
30. {
    
31.     cin>>n>>m;
    
32.     for(int i=1; i<=m; i++)
    
33.     {
    
34.         minv[i] = minv[i-1] + i*i*i;
    
35.         mins[i] = mins[i-1] + i*i*2;
    
36.     }
    
37.     dfs(m, 0, 0, sqrt(n), 28);///20000开三次方开始搜
    
38.     if(flag){
    
39.         cout<<ans;
    
40.         return 0;
    
41.     }
    
42.     cout<<0;
    
43.     return 0;
    
44. }
    

复制代码

胡雨菲菲

1. #include <cstdio>
   
2. #include <cmath>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. const int N2 = 20, INF = 0x7f7f7f7f;
   
6. 
   
7. int N, M, ans = INF, mins[N2], minv[N2];
   
8. 
   
9. void DFS(int d, int s, int v, int lastR, int lastH) {
   
10.     if(!d) {
    
11.         if(v == N) {
    
12.             ans = min(ans, s);
    
13.         }
    
14.         return;
    
15.     }
    
16.     for(int R = min(lastR - 1, (int)(sqrt(N - v))); R >= d; R--) {
    
17.         /*if((2 * (N - v)) / R + s >= ans) { /// WA
    
18.             continue;
    
19.         }*/
    
20.         if(d == M) {
    
21.             s = R * R;
    
22.         }
    
23.         for(int H = min(lastH - 1, (N - v) / (R * R)); H >= d; H--) {
    
24.             int v2 = v + R * R * H;
    
25.             int s2 = s + 2 * R * H;
    
26.             if((2 * (N - v2)) / R + s2 >= ans) {
    
27.                 continue;
    
28.             }
    
29.             if(s2 + mins[d - 1] >= ans) {
    
30.                 continue;
    
31.             }
    
32.             if(v2 + minv[d - 1] > N) {
    
33.                 continue;
    
34.             }
    
35.             DFS(d - 1, s2, v2, R, H);
    
36.         }
    
37.     }
    
38.     return;
    
39. }
    
40. 
    
41. void init(int n) {
    
42.     for(int i = 1; i <= n; i++) {
    
43.         mins[i] = mins[i - 1] + 2 * i * i;
    
44.         minv[i] = minv[i - 1] + i * i * i;
    
45.     }
    
46.     return;
    
47. }
    
48. 
    
49. int main() {
    
50.     scanf("%d%d", &N, &M);
    
51. 
    
52.     init(M);
    
53. 
    
54.     DFS(M, 0, 0, INF, INF);
    
55. 
    
56.     printf("%d", (ans == INF) ? 0 : ans);
    
57.     return 0;
    
58. }
    

复制代码

张笑宇

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. int m,n,ans=999999;
   
5. const int mx=50;
   
6. int mins[mx],minv[mx];
   
7. void dfs(int i,int sums,int sumv,int r,int h)///第i层 表面积sums
   
8. {
   
9.     if (sums+mins[i]>ans) return;
   
10.     else if (sumv+minv[i]>n) return;
    
11.     else if (sums+2*(n-sumv)/r>ans) return;
    
12.     ///三个判断
    
13.     if (i<=0)
    
14.     {
    
15.         if (sumv==n)
    
16.             ans=min(ans,sums);
    
17.         return;
    
18.     }
    
19.     else
    
20.     {
    
21.         for (int ir=r-1; ir>=i; ir--)
    
22.             for (int ih=h-1; ih>=i; ih--)
    
23.             {
    
24.                 int sums0=2*ih*ir;
    
25.                 if (i==m) sums0+=ir*ir;
    
26.                 dfs(i-1,sums+sums0,sumv+ir*ir*ih,ir,ih);
    
27.             }
    
28.     }
    
29. }
    
30. int main()
    
31. {
    
32.     cin>>n>>m;///nπ体积 m层
    
33.     for (int i=1; i<=m; i++)
    
34.     {
    
35.         minv[i]=minv[i-1]+i*i*i;
    
36.         mins[i]=mins[i-1]+2*i*i;
    
37.     }
    
38.     dfs(m,0,0,sqrt(n),n);
    
39.     if (ans==999999) cout<<"0";
    
40.     else cout<<ans;
    
41.     return 0;
    
42. }
    

复制代码

universehyf

1. #include<iostream>
   
2. #include<cstdio>
   
3. #include<cmath>
   
4. using namespace std;
   
5. #define FOR(i,a,b) for(register int i(a);i<=b;++i)
   
6. #define For(i,a,b) for(register int i(a);i>=b;--i)
   
7. int mins[20],minv[20];
   
8. int ans=1<<30,s;
   
9. bool prune(int maxh,int maxr,int n,int v)
   
10. {
    
11.     int cc=0;
    
12.     FOR(i,0,n-1) cc+=(maxh-i)*(maxr-i)*(maxr-i);
    
13.     if(cc<v) return 1;
    
14.     else return 0;
    
15. }
    
16. void dfs(int maxh,int maxr,int n,int v,int m)
    
17. {
    
18.     if(n==0)
    
19.     {
    
20.         if(v) return;
    
21.         ans=min(ans,s);
    
22.     }
    
23.     if(s+mins[n]>ans) return;
    
24.     if(maxh<n||maxr<n) return;
    
25.     if(minv[n]>v)  return;
    
26.     if(prune(maxh,maxr,n,v)) return;
    
27.     For(i,maxr,n)
    
28.     {
    
29.         if(n==m) s=i*i;
    
30.         For(j,maxh,n)
    
31.         {
    
32.             s+=2*i*j;
    
33.             dfs(j-1,i-1,n-1,v-i*i*j,m);
    
34.             s-=2*i*j;
    
35.         }
    
36.     }
    
37. }
    
38. int main()
    
39. {
    
40.     int n,m;scanf("%d%d",&n,&m);
    
41.     FOR(i,1,m)
    
42.         mins[i]=mins[i-1]+2*i*i,
    
43.         minv[i]=minv[i-1]+i*i*i;
    
44.     if(n<minv[m]) printf("0");
    
45.     else
    
46.     {
    
47.         int maxh=(n-minv[m-1])/(m*m)+1;
    
48.         int maxr=sqrt((n-minv[m-1])/m)+1;
    
49.         dfs(maxh,maxr,m,n,m);
    
50.         if(ans==1<<30) printf("0");
    
51.         else printf("%d",ans);
    
52.     }
    
53.     return 0;
    
54. }

复制代码