HKU 2023 Selection Contest G Communist

题目来自 HKU 2023 Selection Contest G。原出处不明。

  This article provides a feasible solution to a certain competitive programming problem.   If you have better solutions, feel free to share with me!

Problem Description

给定一个含有若干个 words 的 article 以及 dictionary，保证：

• article 中的所有 words 都被 dictionary 收录。
• dictionary 中的所有 words 都是 distinct 的。

定义一个消去操作为：选择 article 与 dictionary 中的某个共有子序列 (common subsequence) 并在 article 中将其删去。(例 \(\{a,b,c\}\) 是 \(\{a,x,b,y,c,z\}\) 与 \(\{a,p,b,q,c\}\) 的一个共有子序列)。

求出删去 article 中所有 words 所需的最少消去次数。

Tutorial

将 article 中的 word 替换成其在 dictionary 中出现的次序；问题转化为将 article 序列划分为尽可能少的若干个上升子序列。

采用贪心：从左到右扫描，对于新加入的数，我们要么将其添加至当前所有末尾元素比它小的子序列中末尾元素最大的子序列的末尾，要么新开一个子序列将其作为开头。这两种操作都可以很方便的用 set 维护。

在该贪心算法下得到的子序列数目即为答案。

Code Implementation

#include <bits/stdc++.h>

using namespace std;

map<string, int> dic;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int t;
    cin >> t; cin.ignore();

    while (t--) {
        int n = 0;
        string s, t;
        getline(cin, s);
        getline(cin, t);

        stringstream ss, tt;
        ss << s, tt << t;

        while (tt >> t) dic[t] = ++n;

        multiset<int> st;
        while (ss >> s) {
            int curWord = dic[s];
              if (!st.empty()) {
                set<int>::iterator it = st.lower_bound(curWord);
                if (it != st.begin())
                    st.erase(--it);
            }
            st.insert(curWord);
        }
        cout << st.size() << endl;
    }

    return 0;
}