题目大E意
规定元素顺序为 \(ACGT\). 对于一个仅由 \(A\), \(C\), \(G\), \(T\) 组成的字符串，如果每个位置的元素都满足与前面一个位置相同或排在前面一个位置的元素后面，即可以被称为是 \(form\)-\(1\) 的。如果一个字符串可以拆成一个 \(form\)-\((j-1)\) 和一个 \(form\)-\(1\) 的字符串，则该字符串是 \(form\)-\(j\) 的。给定一个长度为 \(M\) 的字符串，其中一些位置的元素未知，问字典序第 \(R\) 小的 \(form\)-\(K\) 字符串？
重要观察
对于一个长度为 \(n\) 的字符串，它可能属于的 \(form\) 并不一定是唯一的（因为一个 \(form\)-\(1\) 的字符串的任意一个子串也一定是 \(form\)-\(1\) 的），而是一个连续的区间，且该区间的上界是 \(n\)，下界等于\(\sum_2^n{s_{i-1}<s_i}\).
题目解法
这种题一看就是动态规划
\(f (i, j, k)\) 表示考虑从第 \(i\) 位开始的这个后缀满足 \(s_i=k\) 且字符串最小 \(form \leq j\) 的选法个数。转移时我们枚举后面的元素 \(k‘\). 若 \(k \leq k‘\) ，我们将当前位和后面接起来，即 \(f (i, j, k) = f (i+1, j, k‘)\)；否则，\(f (i, j, k) = f (i+1, j-1, k‘)\).
显然，我们可以考虑从头开始考虑每一位的选法。当判断第 \(i\) 位是否可以选择字符 \(c\) 时，我们需要两个信息：(1) 字典序已经比当前选法小的字符串个数 \(cnt\) (2) 前\(i-1\)位最少已经达到\(form\)-\(MIN\). 对于未知的位置我们从小到大试，求出满足条件的后缀选法个数 \(tmp\) ，一旦 \(cnt + tmp \geq R\) 就停止，否则 \(cnt += tmp\). 在确定每个位置的选择后，我们检查是否可以和前面接起来，如果不可以则 \(MIN++\). \(tmp\) 可以用我们预处理出的dp数组计算。同样分两种情况：当前尝试的元素是否能前面接上？若能，要求后缀的 \(form\) 的取值与 \([1,M - cnt + 1]\) 有交集 (aka. \(f (i, M - cnt + 1, c)\))；否则，要求后缀的取值与 \([1,M - cnt]\) 有交集 (aka. \(f (i, M - cnt, c)\)).
我做这道题时坎坷的心路历程
是的我又不过脑子就开始写题了
一开始并没有意识到每个字符串的\(form\)不是唯一的很快口胡出了dp状态就准备开始写（我已经忘了我转移咋写的了）-> 然后意识到会是一个区间但并没有意识到上界其实不用考虑于是在状态里加了一维 -> 然后发现虽然更新 \(cnt\) 时会要求后缀的 \(form\) 在一个范围内，但是后缀的范围只需要有交集即可，不需要完全重合，于是想到新增一个数组维护总方案数，然后再新增两个数组用类似前缀和的方式记录每个后缀 \(form\) 一定大于等于/小于等于一个值的方案数。想过把四维dp降成三维，但是考虑到这样的话一种选法会被两个状态重复计算导致转移出锅。-> 发现看错题了，一开始一直以为\(AG\), \(T\)这种不是一个合法的 \(form\)-\(1\)字符串。但其实要改的地方并不多？-> 终于通过样例，然后MLE了，遂改成滚动数组。-> WA了。这个时候突然意识到上界的问题，恍然大悟，把dp降了一维，写着写着才发现可以推翻之前的很多思路，终于想到了题解中呈现的dp状态。-> 因为一直在同一份代码上改来改去有一些细节忘了改了导致debug了很久才发现一些很傻逼的问题，终于AC.
Morale of the story: 好好看题目给的例子；考虑清楚转移的正确性再开始写；有很大的改动就不要再在原来的代码上修改了。