题目链接：https://www.acwing.com/blog/content/30363/

一. 最长公共子序列

见基础篇-dp

二. 后缀序列

见基础篇-数据结构-表达式求值，这里默认后缀中出现10，表示的是1和0，而不是10

#include <bits/stdc++.h>

using namespace std;

/**
 * Author ：Jaryn
 * Time ：2023/3/4 4:15 下午
 * Desc ：给定一个后缀序列，要求求值，只有加减 输入：23+1+，输出：6
 */

int main() {
    // 思路：利用栈实现表达式求值中，如果是中序序列，那么要用到操作数栈和运算符栈
    // 而这里是后缀，那么用到操作数栈即可
    // 遍历字符串，遇到数字入栈，字符出栈，先出栈的是右操作数
    stack<int> op;
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        if (isdigit(s[i])) op.push(s[i] - '0');
        else if (s[i] == '+') {
            int rNum = op.top(); op.pop();
            int lNum = op.top(); op.pop();
            op.push(lNum + rNum);
        } else if (s[i] == '-') {
            int rNum = op.top(); op.pop();
            int lNum = op.top(); op.pop();
            op.push(lNum - rNum);
        }
    }
    cout << op.top();
    return 0;
}

三. 哈夫曼编码

以字符的出现次数 来构建哈夫曼树
哈夫曼编码长度就是字符串译码后的长度，其实也就是求wpl

wpl又有2种算法：1.叶结点带权路径和 2.所有非叶子结点的权值之和

这里采用2方法，具体可参考贪心-合并果子

#include <bits/stdc++.h>

using namespace std;

/**
 * Author ：Jaryn
 * Time ：2023/3/4 4:29 下午
 * Desc ：给定一个字符串，求哈夫曼编码的最短长度。 输入"aaaaabbbbcccdde"，输出33
 */
int main() {
    unordered_map<char, int> cnt; // 记录字符串中字符出现次数
    priority_queue<int, vector<int>, greater<int>> q; // 小根堆
    string str;
    cin >> str;
    for (auto s : str) {
        cnt[s]++;
    }
    for (auto e : cnt) {
        q.push(e.second);
    }

    int alls = 0; // 所有非叶子结点权值和
    while (q.size() != 1) {
        int min1 = q.top(); q.pop();
        int min2 = q.top(); q.pop();
        alls += min1 + min2;
        q.push(min1 + min2);
    }
    cout << alls;
    return 0;
}