题目描述

乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过50个长度单位。

然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。

请你设计一个程序，帮助乔治计算木棒的可能最小长度。

每一节木棍的长度都用大于零的整数表示。

输入格式

输入包含多组数据，每组数据包括两行。

第一行是一个不超过64的整数，表示砍断之后共有多少节木棍。

第二行是截断以后，所得到的各节木棍的长度。

在最后一组数据之后，是一个零。

输出格式

为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。

数据范围

数据保证每一节木棍的长度均不大于50。

输入样例：

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

输出样例：

6
5

/*
剪枝部分
R(i)-第i层的半径
H(i)-第i层的高度
n-总体积
v-当前已用的体积
优化搜索顺序
先从吃掉体积最大的部分开始搜索，从下往上枚举蛋糕层数，从大到小枚举R,H
排除等效冗余
-暂无
可行性剪枝
1.  设当前枚举到第i层, 
    则存在u<=R(i)<=min{R(i+1)-1,sqrt(n-v)}
    u<=H(i)<=min{H(i+1)-1,(n-v)/R^2}
2.  minv(i)-枚举到第i层所需要的最小体积
    mins(i)-枚举到第i层所需要的最小表面积
    v+minv(i) <= n
    s+mins(i) < ans
最优性剪枝
    观察s(1)+s(2)...+s(i)与n-v的关系
    可以知道s(当前层的面积)+\sum_{i=1}^{u}>2(n-v)/R(u+1)
*/

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

using namespace std;

const int N = 25, INF = 1e9;

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


void dfs(int u, int v, int s) {
    //先剪枝
    if(v + minv[u] > n) return ;
    if(s + mins[u] >= ans) return ;
    if(s + 2*(n-v) / R[u+1] >= ans) return ;

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

    for(int r = min(R[u+1]-1, (int)sqrt(n-v)); r >= u; r--) {
        // cout << "------------" << u << "---------"<< r << endl
        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);
        }
    }
}

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]和R[m+1]中取一个最小值的关系
    R[m+1] = H[m+1] = INF;

    dfs(m, 0, 0);

    if(ans == INF) ans = 0;
    cout << ans << endl;

    return 0;
}