POJ 1190 生日蛋糕

http://poj.org/problem?id=1190

这道题确实写完不知道怎么剪枝了对代码要求很高

仿一波代码

剪枝的地方

1、用mv[]记录最小体积因为越到上面越小那么最小的情况就是最高一层 r = 1 ， h = 1 依次递增但是不确定层数，就像想一个倒置的蛋糕这样每次都去掉最大的一块

　　　　　　　　　　　　保证mv[]记录的总是这个层数所能达到的最小体积 mv[i] = mv[i-1] + r*r*h//很巧妙

　　　　　　　　　　　　这样因为总有 r[i] < r[i-1] , h[i] < h[i-1] 底层的蛋糕 > v / 2 ---->>> v > mv[dep-1] 比这层蛋糕以上所有层的体积都大

2、当前已得表面积 tmp > ans 时剪枝

3、2*v/R+tmp >= ans ; v/R = H*R ---->>>因为再下一层肯定比这层大那么如果再加本层的面积 >= ans 也要减去

4、int Hm = min(H-1, (v-mv[dep-1])/ri/ri); H[i] 满足小于 H[i-1] 并且最大不超过（体积不超过v-mv[dep-1]） (v-mv[dep-1])/ri/ri;//缩小H的范围

 1 #include <iostream>
 2 #include <stdio.h>
 3 #define INF 0x3f3f3f3f
 4 using namespace std;
 5 
 7 int n, m, N, M, ans, tmp;
 8 int mv[28];//记录最小体积
 9 
10 void dfs(int v, int dep, int R, int H)
11 {
12     //从最上层到最下层搜索
13     if (dep == 0)
14     {
15         if (v == 0 && tmp < ans) ans = tmp;
16         return ;
17     }
18     if (v < mv[dep-1] || tmp >= ans || 2*v/R+tmp >= ans) return ;//剪枝
19     for(int ri = R-1; ri >= dep; ri--)
20     {
21         int Hm = min(H-1, (v-mv[dep-1])/ri/ri);
22         for (int hi = Hm; hi >= dep; hi--)
23         {
24             if (v - ri*ri*hi >= 0)
25             {
26                 if (dep == m) tmp = ri*ri;
27                 tmp += 2*ri*hi;
28                 dfs(v-ri*ri*hi, dep-1, ri, hi);
29                 tmp -= 2*ri*hi;
30                 if (dep == m) tmp = 0;
31             }
32         }
33     }
34 }
35 int main()
36 {
37     scanf("%d%d", &n, &m); mv[0] = 0;
38     for (int i = 1; i <= m; i++) mv[i] = mv[i-1]+i*i*i;
39     ans = INF;
40     tmp = 0;
41     dfs(n, m, n+1, n+1);
42     if (ans == INF) printf("0
");
43     else printf("%d
", ans);
44     return 0;
45 }