Poj 1190 生日蛋糕 (DFS 剪枝)

ゞ浴缸里的玫瑰 2022-09-20 13:00 178阅读 0赞

隐约记得前几年网络赛有过类似的题，当时毫无想法……

参考了：http://blog.csdn.net/lencle/article/details/7016191

可能还能进一步优化，可以参考：http://www.cnblogs.com/bisai/archive/2013/06/09/3130171.html

//16ms
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    using namespace std;
    #define min(a,b) ((a)<(b)?(a):(b))
    
    int R,H,n,m;
    int ans; //已搜索到的最优解,即最小面积
    int minv[21];  //i层及以上体积和的最小值
    int tmp; //当前状态的表面积
    
    void DFS (int v,int dep,int R,int H)
    {//v还需要的体积,dep当前层,半径,高度
        if (dep==0)
        {
            if (v==0 && tmp<ans) ans=tmp;
            return;
        }
        if (v-minv[dep-1]<0 || tmp>=ans) return; //剩余体积不足
        if (2*v/R+tmp>=ans) return; //剩余资源的最优解+当前解>=最优解时
        for (int r=R-1;r>=dep;r--)
        {
            int Hm = min(H-1,(v-minv[dep-1])/r/r); //选高度小的情况
            for (int h=Hm;h>=dep;h--)
                if ((v-r*r*h)>=0)
                {
                    if (dep==m) tmp=r*r;  //对于最底层需要考虑底面积
                    tmp+=2*r*h;
                    DFS(v-r*r*h,dep-1,r,h);
                    tmp-=2*r*h;
                }
        }
    }
    
    int main ()
    {
        memset(minv,0,sizeof(minv));
        for (int i=1;i<=m;i++)
            minv[i]=minv[i-1]+i*i*i;
    
        scanf("%d%d",&n,&m);
        ans=0x3fffffff;
        DFS(n,m,sqrt(1.0*n)+1,n+1);
        if (ans==0x3fffffff)
            printf("0\n");
        else
            printf("%d\n",ans);
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，178人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 1011 DFS+剪枝

目是英文的翻译过来大概是这个意思：现在有一些长度相同的棍子，将这些棍子随意切割成n个长度不一的棍子。题目会给出n和这n个棍子的长度，求原来棍子长度的最小值。也可以反...

系统管理员/ 2024年04月19日 11:17/ 0 赞/ 80 阅读

相关 DFS之剪枝与优化 AcWing 168. 生日蛋糕

DFS之剪枝与优化 AcWing 168. 生日蛋糕原题链接 [AcWing 168. 生日蛋糕][AcWing 168.] 算法标签搜索剪枝思

忘是亡心i/ 2024年04月07日 11:42/ 0 赞/ 85 阅读

相关奇偶剪枝+ DFS

<table> <tbody> <tr> <td> <h2>Tempter of the Bone</h2> <strong>Time Limit: 2000

约定不等于承诺〃/ 2024年02月18日 23:05/ 0 赞/ 63 阅读

相关 poj1190（dfs+剪枝）生日蛋糕

生日蛋糕 <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

柔光的暖阳◎/ 2024年02月17日 23:55/ 0 赞/ 77 阅读

相关朋友过生日，用Python给她画了个生日蛋糕

每当有朋友过生日时，生日蛋糕自然是必不可少的，今天我们来看一下如何用 Python 画一个生日蛋糕。本文我们用到的 Python 库包括：turtle、math 和 ran

妖狐艹你老母/ 2023年09月29日 15:32/ 0 赞/ 13 阅读

相关 Python实现生日蛋糕

![format_png][] 来源：http://suo.im/5CtiXr 前言蛋糕的由来：某天在b站上看到某up主，用ipad手绘了一个蛋糕，

野性酷女/ 2022年11月30日 04:06/ 0 赞/ 213 阅读

相关 Poj 1190 生日蛋糕 (DFS 剪枝)

隐约记得前几年网络赛有过类似的题，当时毫无想法…… 参考了：http://blog.csdn.net/lencle/article/details/7016191 可能还能

ゞ浴缸里的玫瑰/ 2022年09月20日 13:00/ 0 赞/ 179 阅读

相关 dfs+剪枝 poj1011

大致题意：给定一堆不定长度的小棒子，问他们能否构成一个正方形。思路：对所有的棒子求和sum之后除以4，得到边长side，问题就转换为求这些棒子能否拼接成4个长度为side的

小咪咪/ 2022年08月03日 16:54/ 0 赞/ 194 阅读

相关 NOI1999 生日蛋糕

include<iostream> include<cstdio> include<cmath> using namespace std; define INF 0x3

桃扇骨/ 2021年12月24日 16:53/ 0 赞/ 308 阅读

相关 168. 生日蛋糕（dfs）

题目链接：[https://www.acwing.com/problem/content/170/][https_www.acwing.com_problem_content_

我不是女神ヾ/ 2021年11月09日 09:36/ 0 赞/ 374 阅读