网站开发面试,淘宝网页版,六安哪家做网站好,苏州建材装修网站建设P1481 魔族密码 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
字典树
在插入字符串 s s s时#xff0c;不断记录 s 0... k s_{0...k} s0...k的个数取最大即可。
#include bits/stdc.h
using namespace std;
const int N 1e5 21;
int cnt[N], tr[N][30], idx,…P1481 魔族密码 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
字典树
在插入字符串 s s s时不断记录 s 0... k s_{0...k} s0...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; cinn;for(int i 0; i n; i) {string s; cins;insert(s);}coutma;
}最长不下降序列LIS
套LIS模板对字符串 s i s_i si和 s j s_j sj来说两者存在从字符串头开始的字串即可更新最值。
#include bits/stdc.h
using namespace std;
int main()
{int n; cinn;vectorint f(n 1);vectorstring vs(n 1);for(int i 1; i n; i) cinvs[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());
}
