Good problem.

题意

题目链接

Monocarp 词典包含 $n$ 个单词，由 $12$ 个拉丁字母组成。单词编号从 $1$ 到 $n$ 。每个单词中的每一对相邻字符都是不同的。对于每个单词 $i$ ，Monocarp 也有一个整数 $c_i$ ，表示他使用这个单词的频率。

Monocarp 想要设计一个键盘，让他可以轻松地输入其中的一些单词。键盘可以表示为一串由 $12$ 个拉丁字母首字母组成的序列，其中从 a 到 l 每个字母正好出现一次。

如果单词中每一对相邻的字符在键盘中也是相邻的，那么就可以用键盘轻松输入单词。键盘的最优性是 $c_i$ 与所有可以用它轻松输入的单词 $i$ 之和。

请帮助 Monocarp 设计出具有最大优化性的键盘。

$1\le n \le 1000, |s_i| \ge 2, \sum |s_i| \le 2000$.

Translated by DeepL

题解

把 12 种字符看成 12 个点，对于给出的一个字符串，如果 $u$ 和 $v$ 相邻的，我们就把他们之间连一条边。这样操作后，如果连成的不是一条链，这个字符串的价值就是一定无法获得的。否则，我们把这个链由头到尾连成一个新字符串，我们发现这个字符串或其首尾翻转后的字符串如果是最终键盘的子串，那么我们就可以获得这个价值。容易知道这样的一个字符串不可能和其翻转串存在于同一个排列中，因此我们可以放心地将他们看作两个价值相同的串进行计算。

现在问题转化为，我们有若干个串，每个串有一个价值，我们需要给出一个 $12$ 个字符的，若这个串是这个排列的子串，则我们就能获得价值，求最大价值。

我们把所有字符串塞进 AC 自动机中，然后在 AC 自动机上跑状压 dp。记一个十二位的 $state$ 表示十二种字符是否被使用过，则 $f[state][u]$ 表示当前状态为 $state$，在 AC 自动机上的 $u$ 点的最大价值。

转移是容易的，同时记录以下到达这个答案的 pre 即可完成输出。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int f[5005][5005];
int pre[5005][5005];
int prechar[5005][5005];
struct ACAM{
    struct Trie_Tree{
        int fail,to[26],val;
    }tr[N];
    int tot=0;
    void insert(string s,int k){
        int l=s.length();
        int u=0;
        for(int i=0;i<l;i++){
            if(!tr[u].to[s[i]-'a']){
                tr[u].to[s[i]-'a']=++tot;
            }
            u=tr[u].to[s[i]-'a'];
        }
        tr[u].val+=k;
    }
    void Get_Fail(){
        queue<int> q;
        for(int i=0;i<26;i++)
            if(tr[0].to[i]) q.push(tr[0].to[i]);
        while(!q.empty()){
            int u=q.front();q.pop();
            for(int i=0;i<26;i++){
                if(tr[u].to[i]){
                    tr[tr[u].to[i]].fail=tr[tr[u].fail].to[i];
                    tr[tr[u].to[i]].val+=tr[tr[tr[u].to[i]].fail].val;
                    q.push(tr[u].to[i]);
                }
                else tr[u].to[i]=tr[tr[u].fail].to[i];
            }
        }
    }
    void solve(){
        for(int i=0;i<=tot;i++){
            for(int j=0;j<(1<<12);j++){
                f[i][j]=-1e9;
                pre[i][j]=-1;
            }
        }
        f[0][0]=0;
        for(int state=0;state<(1<<12);state++){
            for(int i=0;i<=tot;i++){
                if(f[i][state]==-1e9) continue;
                for(int j=0;j<12;j++){
                    if(state&(1<<j)) continue;
                    if(f[tr[i].to[j]][state|(1<<j)]<f[i][state]+tr[tr[i].to[j]].val){
                        f[tr[i].to[j]][state|(1<<j)]=f[i][state]+tr[tr[i].to[j]].val;
                        pre[tr[i].to[j]][state|(1<<j)]=i;
                        prechar[tr[i].to[j]][state|(1<<j)]=j;
                    }
                }
            }
        }
    }
}AC;
int n;
string tmp;
bool ok,vis[N];
int path[15][15],du[15];
void dfs(int u,int fa){
    vis[u]=1;tmp+='a'+u-1;
    for(int v=1;v<=12;v++){
        if(path[u][v]==0) continue;
        if(v==fa) continue;
        if(vis[v]){
            ok=0;
            return;
        }
        else dfs(v,u);
    }
}
void output(int x){
    if(x==0) return;
    output(x>>1);
    putchar('0'+x%2);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    scanf("%d",&n);
    for(int i=1,val;i<=n;i++){
        char s[2005];
        scanf("%d %s",&val,s);

        for(int i=1;i<=12;i++){
            du[i]=vis[i]=0;
            for(int j=1;j<=12;j++){
                path[i][j]=0;
            }
        }
        tmp="";
        for(int j=0;j<strlen(s)-1;j++){
            path[s[j]-'a'+1][s[j+1]-'a'+1]=1;
            path[s[j+1]-'a'+1][s[j]-'a'+1]=1;
        }
        for(int i=1;i<=12;i++){
            for(int j=1;j<=12;j++){
                if(path[i][j]) du[i]++;
            }
        }
        ok=1;
        for(int j=1;j<=12;j++){
            if(du[j]>=3){
                ok=0;
                break;
            }
        }
        if(!ok) continue;

        for(int j=1;j<=12;j++){
            if(du[j]==1){
                dfs(j,j);break;
            }
        }
        for(int j=1;j<=12;j++){
            if(du[j]!=0 && !vis[j]) ok=0;
        }
        if(!ok) continue;
        AC.insert(tmp,val);
        reverse(tmp.begin(),tmp.end());
        AC.insert(tmp,val);
    }
    AC.Get_Fail();
    AC.solve();
    int ans=0,ansid=0;
    for(int i=0;i<=AC.tot;i++){
        if(f[i][(1<<12)-1]>ans){
            ans=f[i][(1<<12)-1];
            ansid=i;
        }
    }
    string ansString;
    int nowstate=(1<<12)-1;
    while(nowstate){
        if(pre[ansid][nowstate]==-1) break;
        char ch=prechar[ansid][nowstate]+'a';
        ansString+=ch;
        ansid=pre[ansid][nowstate];
        nowstate^=(1<<(ch-'a'));
    }
    cout<<ansString<<endl;
    return 0;
}