限号出行

https://codeforces.com/gym/106565/problem/I

题意

给定 \(m\) 条规则，形如 \((x_i,y_i)\) ，表示 \(x_i\) 字符后面不能紧跟着 \(y_i\)

有一个长度为 \(n\) 的字符串，要求从中删除 \(n-k\) 个字符，使得剩下的 \(k\) 个字符组成的字符串满足这 \(m\) 条规则，如果有多解，输出字典序最小，如果无解输出 \(-1\)

思路

考虑逆向DP

\(dp_{i,j}\) 表示第 \(j\) 位到末尾这一段区间内，以 \(i\) 开头的合法串的最长长度

初始化就是，对于 \(j\) 位 \(dp_{s_j,j}=1\) ，其他均为 \(0\)

然后开始逆向递推

逆向对于每一个 \(i\) ，去枚举每一个 \(j\) 字母，可以进行以下递推，意为不选择第 \(i\) 位的字母，第 \(i\) 位直接从 \(i+1\) 继承过来

\(dp_{j,i}=max(dp_{j,i},dp_{j,i+1})\)

其次如果想要选择第 \(i\) 位的字母，要满足第 \(i\) 位的字母与第 \(i+1\) 位的 \(j\) 字母没有任何规则限制，则有以下递推

\(dp_{s_i,i}=max(dp_{s_i,i},dp_{j,i+1}+1)\)

计算答案就设置一个指针 \(i\) 最初指向 \(0\) ，从最终字符串第一位开始枚举 \(now\) 是否可以是 \(a,b,c,...\) 找到第一个满足 \(dp_{i,now}\geq k\) 的字母，然后把指针从 \(0\) 往后扫找到第一个 \(s_i = now\) 的 \(i\) ，然后把指针挪到 \(i+1\) 的位置，然后把 \(k\) 减一，循环往复直到找齐 \(k\) 个字母，能让字典序最小

代码

#include<bits/stdc++.h>
#define Maxn 200000
using namespace std;
int dp[26][Maxn+5];
char s[Maxn+5];
map<pair<int,int>,int> mp;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        mp.clear();
        int n,m,k;
        cin>>n>>m>>k;
        cin>>s;
        while(m--)
        {
            char x,y;
            cin>>x>>y;
            mp[make_pair(x-'a',y-'a')]=1;
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<26;j++)
            {
                dp[j][i]=(s[i]-'a'==j);
            }
        }
        for(int i=n-2;i>=0;i--)
        {
            for(int j=0;j<26;j++)
            {
                if(!mp[make_pair(s[i]-'a',j)])
                {
                    dp[s[i]-'a'][i]=max(dp[s[i]-'a'][i],dp[j][i+1]+1);
                }
                dp[j][i]=max(dp[j][i],dp[j][i+1]);
            }
        }
        // for(int i=0;i<n;i++)
        // {
        //     for(int j=0;j<26;j++)
        //     {
        //         cout<<dp[j][i]<<" ";
        //     }
        //     cout<<endl;
        // }
        bool pass=true;
        for(int i=0;i<26;i++)
        {
            if(dp[i][0]>=k) pass=false;
        }
        if(pass)
        {
            cout<<"-1"<<endl;
            continue;
        }
        int i=0,pre=-1;
        while(k)
        {
            for(int j=0;j<26;j++)
            {
                if(dp[j][i]>=k&&!mp[make_pair(pre,j)])
                {
                    pre=j;
                    k--;
                    while(s[i]-'a'!=j) i++;
                    cout<<s[i++];
                    break;
                }
            }
        }
        cout<<endl;
    }
    return 0;
}