算法刷题

AcWing 168. 生日蛋糕(搜索)

2020-04-03  本文已影响0人  良木lins

深度优先搜索 + 剪枝

原题链接

感悟:本题的小细节还挺多的,也正是利用这些题目给的小细节来增加剪枝条件的。这个题是我第一次遇到需要一些数学式子推到的题目,尽管不难,但第一次碰到也很蒙,虽然数学的学习还算可以,但应用到一些实际东西上还是无从下手,得加强加强。

NOTE
: 本题都带有pai,且题目最后不用输出,则一起全部舍去

题目思路
剪枝优化
证明

(到时候补一张图,确实有点麻烦)

ACcode

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 25, INF = 1e9;//这种无穷挺好啊

int n, m;
int minv[N], mins[N]; //存放每层最小r,h
int R[N], H[N];       //存放枚举中使用的r,h,最后只会剩下一组最优解
int ans = INF;

void dfs(int u, int v, int s)
{
     //剪枝(可行性):当前层体积的极限关系
    if(minv[u] + v > n) return;    
     //剪枝(最优性):当前层面积与已知最优的关系
    if(mins[u] + s >= ans) return;
    
     //剪枝(可行性):当前体积与面积之间的关系
    if(s + 2*(n-v)/R[u+1] >= ans) return;
    
     //返回条件
    if(!u)
    {
        if(v == n) ans = s;
        return;
    }
    
     //枚举顺序:1.从大到小 2.先r后h
    for(int r = min((int)sqrt(n-v), R[u+1] - 1); r >= u; r--)
        for(int h = min((n-v)/(r*r), H[u+1] - 1); h >= u; h--)
        {
            int t = 0;
            if(u == m) t = r * r;
            R[u] = r; H[u] = h;
            dfs(u-1, v + r * r * h, s + 2 * r * h + t);
        }
}

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= m; i++)
    {
        minv[i] = minv[i - 1] + i * i * i;
        mins[i] = mins[i - 1] + 2 * i * i;
    }
    
    R[m + 1] = H[m + 1] = INF;
    dfs(m, 0, 0);
    
    cout << ans << endl;
    
    return 0;
}
上一篇 下一篇

猜你喜欢

热点阅读