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

tag:
动态规划，递归，枚举，区间DP，NOIP提高组，2003

思路：
使用区间dp的思路，令 f[i][j] 为节点i到节点j之间最大的加分，并用 root[i][j] 记录下这段区间的根节点。之后遍历每一种可能的区间，依据题目的公式更新数组f记录root最后得出结果输出 f[1][n] 即表示给定的二叉树tree的最高加分。然后再输出该情况时树的前序遍历即可。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 31;
int h[N], e[N * 2], ne[N * 2], idx;
int n;
LL f[N][N];
int root[N][N];
void print(int l ,int r)
{
    if (l > r) return;
    cout << root[l][r] << ' ';
    if (l == r) return;
    print(l, root[l][r] - 1),print(root[l][r] + 1, r);
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> f[i][i], root[i][i] = i;
    for (int len = 1; len <= n; len ++)
        for (int i = 1; i + len <= n; i ++)
        {
            int j = i + len;
            f[i][j] = f[i + 1][j] + f[i][i];
            root[i][j] = i;
            for (int k = i + 1; k <= j; k ++)
            {
                if (f[i][j] < f[i][k - 1] * f[k + 1][j] + f[k][k])
                {
                    f[i][j] = f[i][k - 1] * f[k + 1][j] + f[k][k];
                    root[i][j] = k;
                }
            }
        }
    cout << f[1][n] << endl;
    print(1, n);
    return 0;
}

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

tag:
递归， 二叉树

代码：

#include <iostream>
#include <string>
using namespace std;

string inorder, preorder;

void buildPostorder(int inStart, int inEnd, int preStart, int preEnd) {
    // 若范围无效，则返回
    if (inStart > inEnd || preStart > preEnd) {
        return;
    }

    // 前序遍历的第一个元素即为根节点
    char root = preorder[preStart];

    // 在中序遍历中找到根节点的位置
    int rootIndex = -1;
    for (int i = inStart; i <= inEnd; ++i) {
        if (inorder[i] == root) {
            rootIndex = i;
            break;
        }
    }

    // 根节点左边的节点个数
    int leftTreeSize = rootIndex - inStart;

    // 递归处理左子树
    buildPostorder(inStart, rootIndex - 1,
                   preStart + 1, preStart + leftTreeSize);

    // 递归处理右子树
    buildPostorder(rootIndex + 1, inEnd,
                   preStart + leftTreeSize + 1, preEnd);

    // 最后输出根节点，实现后序遍历顺序：左子树 -> 右子树 -> 根
    cout << root;
}

int main() {
    // 输入中序遍历和前序遍历字符串
    cin >> inorder >> preorder;

    int n = inorder.size();
    buildPostorder(0, n - 1, 0, n - 1);

    return 0;
}