首页 > 其他 > 详细

[NOI1999]生日蛋糕

时间:2018-10-04 23:43:47      阅读:102      评论:0      收藏:0      [点我收藏+]

标签:clas   span   剪枝   -i   ()   蛋糕   line   描述   namespace   

【题目描述】:
[NOI1999]生日蛋糕

【思路】:
比较经典的搜索+剪枝题目。
要求蛋糕最小的表面积(不算下底面)。由俯视图可知,上面的表面积=下底面表面积,于是我们可以预处理出来,之后就只用求侧面积。然后进行逐层搜索。

\(sums_i\)表示第\(i\)层最小的表面积,\(sumv_i\)表示第\(i\)层最小体积,设最底层为第\(n\)层,枚举每一层。我们可以得到以下剪枝:

  • 如果当前搜索到的最小表面积已经大于了已知的最小表面积,则没有必要再继续搜索下去,直接\(return\)
  • 如果当前搜索到的体积已经超过题目限制,则再搜下去一定是错解,\(return\)
  • 如果由体积推出来当前的表面积已经不优,则\(return\)
  • 由题目限制,下面一层的\(r,h\)都要大于上面一层的\(r,h\)。那么我们可以得到一个搜索的区间,只在这个区间搜索
#include<cstdio>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;

int n,m;
const int MAXN = 20;
int sums[MAXN];int sumv[MAXN];int ans = inf;

inline void dfs(int now/*当前层数*/,int r/*当前半价*/,int h/*当前高度*/,int s/*当前表面积*/,int v/*当前体积*/){
    int real;
    if(now == 0){//搜索到头,更新答案
        if(v == n && ans > s){
            ans = s;
        }
        return ;
    }
    
    if(s + sums[now - 1] >= ans || v + sumv[now - 1] > n || 2*(n-v)/r + s >= ans) return ;//见剪枝1,2,3
    
    for(int i=r-1;i>=now;--i){//枚举的上下界
        if(now == m) s = i * i;
        real = min(h-1 , (n-sumv[now-1]-v)/i/i);
        for(int j=real;j>=now;--j){
            dfs(now-1,i,j,s+2*i*j,v+i*i*j);
        }
    }
}

inline void work(){
    for(int i=1;i<=m;++i){//预处理
        sums[i] = sums[i-1] + 2*i*i;
        sumv[i] = sumv[i] + i*i*i;
    }
    dfs(m,n,n,0,0);
}

int main(){
    scanf("%d%d",&n,&m);
    work();
    if(ans == inf) puts("0");
    else printf("%d",ans);
    return 0;
}

[NOI1999]生日蛋糕

标签:clas   span   剪枝   -i   ()   蛋糕   line   描述   namespace   

原文:https://www.cnblogs.com/lajioj/p/9743735.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号