题意:想做一个m层(每层是一个圆柱)总体积为n*pi的蛋糕抹奶油,想使得抹的奶油的面积/pi = s最小,问最小的s是多少。
题解:化简下得到sigma(ri * ri * hi)= n,s =sigma(2 * ri * hi) + h1 * h1,由于所有的数据都是不确定的没办法dp,只能暴搜了。
很普通的一个剪枝是当前的值+未得到的最小值 >= ans直接跳出,开始从上到下dfs,但是一直TLE,然后看别人代码是从下向上dfs的,
我想是因为大的放在下面的时候剩余需要填充的体积减少的很快,这样会减少dfs的深度。
Sure原创,转载请注明出处。
#include <iostream> #include <cstdio> #include <memory.h> #include <cmath> #define MIN(a , b) ((a) < (b) ? (a) : (b)) using namespace std; const int inf = 1 << 29; int m,n,ans; void dfs(int v,int c,int sr,int sh,int sum) { if(c == m) { if(sum < ans) { ans = sum; } return; } if(sum + 2 * v / sr >= ans) return; //估计剩下的最大的答案剪枝 for(int i=sr;i>=m-c;i--) { int bj = v / (i * i) + 1; //剩下部分的最大h if(sh < bj) bj = sh; if(i * i * bj * (m - c) < v) break; //是否能构成v的体积 if(c == 0) sum = i * i; for(int j=bj;j>=m-c;j--) { if(i * i * j + (i-1) * (i-1) * (j-1) * (m - c - 1) < v) break; //是否能构成v的体积 if(c < m-1 || i * i * j == v) { dfs(v - i * i * j , c+1 , i-1 , j-1 , sum + 2 * i * j); } } } return; } int main() { while(~scanf("%d %d",&n,&m)) { ans = inf; int rmax = sqrt(1.0 * n / m) + 1; int hmax = n / m + 1; dfs(n,0,rmax,hmax,0); if(ans == inf) ans = 0; printf("%d\n",ans); } return 0; }