题解 P1731 【[NOI1999]生日蛋糕】

zqiceberg · 2020-01-07 16:31:32 · 题解

算法

dfs( )

分析

搜索框架：从下往上搜索，枚举每层的半径和高度作为分支。

剪枝

1.上下界剪枝

2.优化搜索顺序

3.可行性剪枝

4.最优性剪枝

搜索过程中的剪枝，其实就是针对“维度”与该维度的边界条件，加以缩放、推导，得出一个相应的不等式，来减少所搜书分支的扩张。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 25, INF = 1e9;

int n, m;
int minv[N], mins[N];
int R[N], H[N];
int ans = INF;

void dfs(int u, int v, int s)//从第u层开始，当前体积v，当前面积s
{
    if (v + minv[u] > n) return ;  //体积大于n，剪枝
    if (s + mins[u] >= ans) return ; //面积比当前ans大，剪枝
    if (s + 2 * (n - v) / R[u + 1] >= ans) return ; //最优性剪枝 算法进阶指南P108

    if (!u)
    {
        if (v == n) ans = s;
        return ;
    }

    for (int r = min(R[u + 1] - 1, (int)sqrt(n - v)); r >= u; r--)
        for (int h = min(H[u + 1] - 1, (n - v) / r / r); 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);//从第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;    //体积：i*i  *i
        mins[i] = mins[i - 1] + 2 * i * i;    //面积：2*i  *i
    }

    R[m + 1] = H[m + 1] = INF;

    dfs(m, 0, 0);//从第m层开始，当前体积和面积都是0

    cout << ans << endl;

    return 0;
}