P1481 魔族密码

P1481 魔族密码 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

字典树

在插入字符串$s$时，不断记录$s_{\mathrm{0...}k}$的个数取最大即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 21;
int cnt[N], tr[N][30], idx,ma;
void insert(string s) {
    int u = 0, res = 0;
    for(auto &t: s) {
        int p = t - 'a';
        if(!tr[u][p]) tr[u][p] = ++idx;
        u = tr[u][p];
        // 加上当前结点的所有字符串
        res += cnt[u];
    }
    cnt[u]++;
    res++; // 加上当前字符串
    ma = max(res, ma);
}
int main()
{
    int n; cin>>n;
    for(int i = 0; i < n; ++i) {
        string s; cin>>s;
        insert(s);
    }
    cout<<ma;
}

最长不下降序列（LIS）

套LIS模板，对字符串$s_i$和$s_j$来说，两者存在从字符串头开始的字串即可更新最值。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n; cin>>n;
    vector<int> f(n + 1);
    vector<string> vs(n + 1);
    for(int i = 1; i <= n; ++i) cin>>vs[i];
    for(int i = 1; i <= n; ++i) {
        f[i] = 1;
        for(int j = 1; j < i; ++j) {
            if(vs[j].substr(0, vs[i].size()) == vs[i] || vs[i].substr(0, vs[j].size()) == vs[j] ) f[i] = max(f[i], f[j] + 1);
        }
    }
    cout<<*max_element(f.begin(), f.end());
}