wa,0pts
查看原帖
wa,0pts
384214
esquigybcu楼主2021/7/29 22:08
#include <stdio.h>
#include <math.h>
#include <limits.h>
#include <algorithm>
// why is min in <algorithm>? 
using std::min;

const int SIZE = 20;
int ans = INT_MAX, n, m;

inline int min_vol(int n) // sum(i = 1 -> n) i ^ 3
{
    return n * n * (n + 1) * (n + 1) / 4;
}

inline int min_area(int n) // 2 * sum(i = 1 -> n) i ^ 2
{
    return n * (n + 1) * (n * 2 + 1) / 3;
}

void dfs(int layers, int cur_vol, int cur_area, int last_h, int last_r)
{
    if (layers == m)
    {
        if (cur_vol == n)
            ans = min(ans, cur_area);
        return;
    }
    // cut branch
    if (cur_area + 2 * (n - cur_vol) / last_r > ans)
        return;
    if (cur_vol + min_vol(m - layers) > n)
        return;
    if (cur_area + min_area(m - layers) > ans)
        return;
    
    for (int i = last_r - 1; i >= m - layers /*(!)*/; i--)
    {
        if (layers == 0)
            cur_area = i * i; // top
        int max_h = min(last_h - 1, (n - cur_vol - min_vol(m - layers - 1)) / (i * i));
        for (int j = max_h; j >= m - layers /*(!)*/; j--)
            dfs(layers + 1, cur_vol + i * i * j, cur_area + 2 * i * j, j, i);
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    int max_r = sqrt(n);
    dfs(m, 0, 0, n, max_r);
    printf("%d", ans == INT_MAX ? 0 : ans);
    return 0;
}

差不多是照着这篇题解打的

2021/7/29 22:08
加载中...