洛谷P1731 生日蛋糕

url: https://www.luogu.com.cn/problem/P1731

tag:
NOI1999，dfs，剪枝，搜索

思路：
使用dfs和剪枝。dfs有四个参数，分别表示第几层，剩余体积，当前的面积，剩余层数。剪枝是有两个，第一个，如果当前的表面积加上之后最小的面积大于当前的面积，就return，第二个，之后最大的体积小于剩余的体积就return。边界情况是当剩余体积v小于0，return；当前层数超过m，return；当前的面积大于最小面积，return。终止条件是当剩余体积v == 0，然后层数等于m时表面积加上每层的上表面积（其实就是第一层蛋糕的顶层表面积），然后更新minv。考虑特殊情况，如果层数为1则直接遍历半径r，然后找到一个最小的表面积。

代码：

#include <iostream>
#include <cmath>
using namespace std;
int n, m, minv = 0x3f3f3f3f;
int r[20], h[20];
void dfs(int u, int v, int c, int p)
{
    if (v < 0) return;
    if (u > m + 1) return;
    if (c >= minv) return;

    if (v == 0 && u == m + 1)
    {
        c += r[1] * r[1];
        minv = min(minv, c);
        return;
    }

    if (c + p + r[1] * r[1] > minv) return;

    if (v - (r[u - 1] * r[u - 1] * h[u - 1] * p) > 0) return;

    for (int i = r[u - 1] - 1; i >= p; i--)
    {
        for (int j = h[u - 1] - 1; j >= p; j --)
        {
            if (v - i * i * j >= 0 && u + 1 <= m + 1)
            {
                r[u] = i;
                h[u] = j;

                dfs(u + 1, v - i * i * j, c + 2 * i * j, p - 1);

                r[u] = 0;
                h[u] = 0;
            }
        }
    }
}
int main()
{
    cin >> n >> m;
    if (m == 1)
    {
        for (int r = 1; r <= sqrt(n); r ++)
        {
            if (n % (r * r) == 0)
            {
                int h = n / (r * r);
                int tmp = 2 * r * h + r * r;
                minv = min(minv, tmp);
            }
        }
        if (minv == 0x3f3f3f3f) cout << 0;
        else cout << minv;
        return 0;
    }
    r[0] = (int)sqrt(n);
    h[0] = (int)sqrt(n);
    dfs(1, n, 0, m);
    if (minv == 0x3f3f3f3f) cout << 0;
    else cout << minv;
    return 0;
}