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());
}