CF178F3 Representative Sampling 题解
题目链接:CF178F3 Representative Sampling
题意:
有 \(n\) 个字符串 \(a_i\) ,从中选取 \(k\) 个,使它们两两之间的 \(\text{LCP}\)(最长公共前缀)之和最大。输出这个最大值。
\(k\le n\le 2000,|a_i|\le 500\)
看到最长公共前缀我还愣了一下,这不裸的 \(\tt{trie}\)
树吗,然后想了半天不会。。
考虑建 \(\tt{trie}\) 树然后在上面做树上背包
注意这里背包能选的“物品”只有 \(\tt{trie}\) 树上「是字符串结尾的结点」
方便起见,称「是字符串结尾的结点」为「串结点」
两两串结点的贡献,也就是他们的最长公共前缀(LCP)长度,其实就是他们的LCA深度。
记 \(i\) 的子结点 \(c_1,c_2,\cdots,c_{\lambda_i}\) ,设 \(f_{c_k,j}\) 表示以 \(i\) 为根的子树中,只考虑 \(c_1,c_2,\cdots,c_k\) ,选 \(j\) 个串结点,「两两串结点的LCA」的深度之和(\(i\) 深度为 \(0\) ),
设 \(g_{i,j}\) 表示以 \(i\) 为根的子树中,选 \(j\) 个串结点,「两两串结点的LCA」的深度之和 (\(i\) 深度为 \(0\) ),则 \[ f_{c_k,j} = \max\limits_{0 \le l \le \min \{j,\text{size}(c_k)\}} \left\{f_{c_{k-1},j-l}+g_{c_k,l}+\dbinom{l}{2}\right\} \] 注意到两个串只会在他们的LCA处更新dp值,因此有很多结点都是没用的
我们直接把这棵树缩成一个带权树,保留可以成为LCA的结点
于是我们就可以 \(O(n^2)\) 通过这题了
u1s1,代码是学的yhx巨佬的1,懒得改了(
代码:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e3+15)
#define S (int)(555)
#define L (int)(1e6+15)
string s;
int n,m,tot=1,cnt,ed[L],val[L],id[L];
int o[L],sz[L],trie[L][26],f[N*3][N],g[N*3][N];
void up(int &x,int y){ x < y ? x = y : 0;}
int C2(int x){return x*(x-1)>>1;}
void insert(string s)
{
int u=1;
for(int i=0; i<s.size(); i++)
{
int c=s[i]-'a';
if(!trie[u][c]) trie[u][c]=++tot;
u=trie[u][c];
}
++ed[u];
}
void dfs(int u)
{
id[++cnt]=u; o[u]=cnt;
sz[u]=ed[u]; int v,la=0;
for(int i=0; i<26; i++)
if((v=trie[u][i])!=0)
{
dfs(v);
sz[u]+=sz[v];
}
int lim=min(sz[u],m);
for(int i=0; i<26; i++)
if((v=trie[u][i])!=0)
{
for(int j=lim; j>=1; j--)
for(int k=0; k<=j && k<=sz[v]; k++)
up(f[o[v]][j],f[o[la]][j-k]+g[o[v]][k]+C2(k)*(val[v]+1));
la=v;
}
memcpy(g[o[u]],f[o[la]],N<<2);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> m;
for(int i=1; i<=n; i++)
{
cin >> s;
insert(s);
}
for(int i=tot,j,k; i>1; i--)
if(!ed[i])
{
for(j=k=0; j<26; j++)
if(trie[i][j]) {if(k)break; k=trie[i][j];}
if(j==26&&(!ed[k]))
{
val[i]=val[k]+1;
memcpy(trie[i],trie[k],26<<2);
}
}
dfs(1);
cout << g[1][m] << '\n';
return 0;
}
参考文献:
https://yhx-12243.github.io/OI-transit/records/cf178F3.html↩︎