1130. 叶值的最小代价生成树

1130.叶值的最小代价生成树

题目描述：

给出一个正整数数组arr，考虑所有满足以下条件的二叉树：

• 每个节点都有 $0$ 个或 $2$ 个节点。
• 数组 arr中的值与树的中序遍历中每个叶节点的值一一对应。
• 每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。

数据范围：

$2\le arr.len \le 40,1\le arr[i] \le 15$

题解：

动态规划：

可以发现，只要数组的长度大于等于 $2$ 就一定存在对应的二叉树。因此可以合并两个相邻的区间更新答案，可以使用区间dp。用区间dp，直接从区间长度为 $2$ 开始遍历，也没有问题。

$$dp[i][j] = \min(dp[i][j], dp[i][k] + dp[k + 1][j] + \max\_arr[i][k] \times \max\_arr[k + 1][j])\\$$

区间dp，枚举区间 $len \in [2, n]$ ，枚举区间左端点 $i \in [0, n - len + 1)$ ， $i$ 从 $0$ 到 $i + len - 1 \lt n$ ，这样的话得到区间右端点 $j = i + len - 1$ 。最后枚举区间断点 $k\in [i, j)$ 。因为是 $k + 1$ ，所以不能枚举到 $j$ 。

初始条件，因为区间长度为 $1$ 不符合条件，区间长度为 $2$ 时等于直接相乘，所以长度为 $1$ 的区间初始化为 $0$ 。

单调栈做法：

先合并的深度更大，后面被乘的次数更多。因此需要把小的先合并。选择极小值，然后看两侧哪个数字比较小，和更小的一个合并。使用单调减栈，维护递减序列。如果遇到一个大于栈顶的元素 $x$ ，就弹出栈顶元素 $y$ ，然后判断当前元素 $x$ 和当前栈顶元素 $z$ 的大小，如果 $x < z$ 则合并 $x$ 与 $y$ ，加上合并的代价，把 $x$ 入栈；否则合并 $y$ 与 $z$ ，把 $z$ 入栈，把 $x$ 入栈。

感觉有点类似哈夫曼编码。

代码：

auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 4e1 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    int dp[maxn][maxn];
    int maxl[maxn][maxn];
    int mctFromLeafValues(vector<int> &arr)
    {
        int n = arr.size();
        // 区间 dp
        for (int i = 0; i < n; ++i)
            for (int j = i; j < n; ++j)
            {
                if (i == j)
                    dp[i][j] = 0;
                else
                    dp[i][j] = INF;
            }
        for (int i = 0; i < n; ++i)
        {
            int maxx = arr[i];
            for (int j = i; j < n; ++j)
            {
                maxx = max(maxx, arr[j]);
                maxl[i][j] = maxx;
            }
        }
        for (int len = 2; len <= n; ++len)
        {
            for (int i = 0; i + len - 1 < n; ++i)
            {
                int j = i + len - 1;
                for (int k = i; k < j; ++k)
                {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + maxl[i][k] * maxl[k + 1][j]);
                }
            }
        }
        return dp[0][n - 1];
    }
};

auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 4e1;
    int st[maxn];
    int top = -1;
    int mctFromLeafValues(vector<int> &arr)
    {
        int n = arr.size();
        int ans = 0;
        for (int i = 0; i < n; ++i)
        {
            while (top >= 0 && st[top] <= arr[i])
            {
                int y = st[top--];
                if (top < 0 || st[top] > arr[i])
                {
                    ans += arr[i] * y;
                }
                else
                {
                    ans += st[top] * y;
                }
            }
            st[++top] = arr[i];
        }
        while (top >= 1)
        {
            int y = st[top--];
            ans += y * st[top];
        }
        return ans;
    }
};