题目一眼望去这道题是一道dp但是答案要求输出字典序最小的子序列所以在设计dp上要做些功夫。设dp[i]表示从位置i到末尾能构成的最长的合法子序列的长度。注意这里dp存的是长度。考虑如何转移假设某个位置我要放字母c我如果想让最长子序列最长最好是能把这个字母c往前放这样能给后方的字母留出更多的位置。由于题目说挑选的是长度为k的子序列所以转移的时候可以从之前的多个位置转移所以有必要设计一个辅助数组nxt[i][c]表示右侧距离第i位最近的字母c出现的位置那么状态转移方式就是 时间复杂度O26*n空间复杂度O(26*n)有注释的代码#includebits/stdc.h using namespace std; void solve (){ int n,m,k; string s; cinnmks; vectorvectorintok(26,vectorint(26,1));//ok[i][j]表示可以从字母i转移到字母j for (int i1;im;i){ char u,v; cinuv; ok[u-a][v-a]0; } vectorvectorintnxt(n1,vectorint(26,1e8));//用于记录距离当前位置右侧最近的某个字母的下标 s s; for (int i1;in;i){ nxt[i][s[i]-a]i; } //倒序遍历初始化nxt数组 for (int in-1;i1;i--){ for (int c0;c26;c){ nxt[i][c]min(nxt[i1][c],nxt[i][c]); } } //dp核心逻辑倒序遍历内层遍历字母利用nxt从右侧所有可能的位置最找最大值 vectorintdp(n1,0); for (int in;i1;i--){ int maxn0; for (int c0;c26;c){ if (!ok[s[i]-a][c])continue; if (i1nnxt[i1][c]!1e8)maxnmax(maxn,dp[nxt[i1][c]]); } dp[i]1maxn; } //构建子序列由于字典序最小所以从a-z遍历的时候一旦符合要求就break当尝试字母c时看一下nxt[i1][c]也就是这个字母的位置到末尾最多能组成多长的序列而这一步可以用dp[nxt[i1][c]]查询得到 string h; for (int pos0;posn;){ if (h.size()k)break; bool found0; for (int c0;c26;c){ if (!h.empty()!ok[h.back()-a][c])continue; if (pos1nnxt[pos1][c]!1e8dp[nxt[pos1][c]]k-h.size()){ h.push_back(char(ca)); posnxt[pos1][c]; found1; break; } } if (!found)break; } if (h.size()k)couth\n; else cout-1\n; } int main () { ios::sync_with_stdio(0); cin.tie(0); int t; cint; while (t--){ solve (); } } 题目一眼望去这道题是一道dp但是答案要求输出字典序最小的子序列所以在设计dp上要做些功夫。设dp[i]表示从位置i到末尾能构成的最长的合法子序列的长度。注意这里dp存的是长度。考虑如何转移假设某个位置我要放字母c我如果想让最长子序列最长最好是能把这个字母c往前放这样能给后方的字母留出更多的位置。由于题目说挑选的是长度为k的子序列所以转移的时候可以从之前的多个位置转移所以有必要设计一个辅助数组nxt[i][c]表示右侧距离第i位最近的字母c出现的位置那么状态转移方式就是 时间复杂度O26*n空间复杂度O(26*n)有注释的代码#includebits/stdc.h using namespace std; void solve (){ int n,m,k; string s; cinnmks; vectorvectorintok(26,vectorint(26,1));//ok[i][j]表示可以从字母i转移到字母j for (int i1;im;i){ char u,v; cinuv; ok[u-a][v-a]0; } vectorvectorintnxt(n1,vectorint(26,1e8));//用于记录距离当前位置右侧最近的某个字母的下标 s s; for (int i1;in;i){ nxt[i][s[i]-a]i; } //倒序遍历初始化nxt数组 for (int in-1;i1;i--){ for (int c0;c26;c){ nxt[i][c]min(nxt[i1][c],nxt[i][c]); } } //dp核心逻辑倒序遍历内层遍历字母利用nxt从右侧所有可能的位置最找最大值 vectorintdp(n1,0); for (int in;i1;i--){ int maxn0; for (int c0;c26;c){ if (!ok[s[i]-a][c])continue; if (i1nnxt[i1][c]!1e8)maxnmax(maxn,dp[nxt[i1][c]]); } dp[i]1maxn; } //构建子序列由于字典序最小所以从a-z遍历的时候一旦符合要求就break当尝试字母c时看一下nxt[i1][c]也就是这个字母的位置到末尾最多能组成多长的序列而这一步可以用dp[nxt[i1][c]]查询得到 string h; for (int pos0;posn;){ if (h.size()k)break; bool found0; for (int c0;c26;c){ if (!h.empty()!ok[h.back()-a][c])continue; if (pos1nnxt[pos1][c]!1e8dp[nxt[pos1][c]]k-h.size()){ h.push_back(char(ca)); posnxt[pos1][c]; found1; break; } } if (!found)break; } if (h.size()k)couth\n; else cout-1\n; } int main () { ios::sync_with_stdio(0); cin.tie(0); int t; cint; while (t--){ solve (); } } 
