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巨佬的¹，懒得改了（

代码：

#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 ↩