Codeforces Gym102001 J. Future Generation
题意：
给定\(n\)个字符串\(S_1,S_2,\dots,S_n\)
现在要寻找这\(n\)个串的子序列\(A_1,A_2,\dots,A_n\)
满足\(A_1<A_2<\dots<A_n\)（按字典序从小到大），使得这\(n\)?个子序列长度之和最大，输出长度最大值。
分析：
由于\(n\)最大为\(15\)，每一个字符串的长度最大也是\(15\)，可以考虑枚举子序列。
设\(S_i\)?的非空子序列为\(S_{i,j}(1\leq j< 2^{|S_i|})\)?
不妨设\(S_{i,j}\leq S_{i,j+1}\)（字典序不减）
那么考虑动态规划设计状态，\(f(i,j)\)表示考虑前\(i\)个字符串，其中第\(i\)个字符串取\(S_{i,j}\)这一个子串的最优解。
转移方程容易写出
设\(m=\max\limits_{1\leq i\leq n}|S_i|\)??，如果直接朴素地利用这个式子转移，会发现转移一次的代价是\(O(2^{m})\)??的，状态数量是\(O(2^{m}\cdot n)\)??
那么时间复杂度将会是\(O(n\cdot 4^{m})\)??，这个时间复杂度有些无法接受。
我们不妨设\(dp(i,j)=\max\limits_{1\leq k\leq j}f(i,k)\)，设满足\(S_{i-1,k}<S_{i,j}\)最大的\(k\)为\(k_m\)
上面的式子可以变成
关于\(dp(i,j)\)，还有一个转移方程
将上式代入下式，可以得到
只要我们在转移过程中能够处理\(k_m\)的计算问题，那么时间复杂度将会有很大的优化。
之前我们定义的\(S_{i,j}\)关于\(j\)单调不减，所以随着\(j\)增大，\(k_m\)也是不减的。可以采用双指针的方式，当\(j\)?移动到\(j+1\)时，\(k_m\)无需从头开始找，只要从当前位置向后找即可。所以对于给定的\(i\)，所有的\(j\)转移代价最坏为\(O(2^m)\)?，此时时间复杂度为\(O(n\cdot 2^m)\)，这个复杂度就可以接受了。
代码：
#include <algorithm>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string str[20];
vector<string> substr[20];
int dp[20][1 << 16];
using namespace std;
int main() {
int n;
cin >> n;
// substr[i]为str[i]的所有子序列，并排序
for (int i = 1; i <= n; i++) {
cin >> str[i];
substr[i].push_back("");
for (int j = 0; j < str[i].size(); j++) {
int siz = substr[i].size();
for (int k = 0; k < siz; k++) {
substr[i].push_back(substr[i][k] + str[i][j]);
}
}
sort(substr[i].begin(), substr[i].end());
}
memset(dp, 0xc0, sizeof(dp)); // 给dp赋极小值0xc0c0c0c0=-1061109568
for (int i = 1; i < substr[1].size(); i++) {
dp[1][i] = max(dp[1][i - 1], (int)substr[1][i].size());
}
// 此处的k是第一个不符合substr[i-1][k]<substr[i][j]的k，所以k_m=k-1
for (int i = 2; i <= n; i++) {
int k = 1;
for (int j = 1; j < substr[i].size(); j++) {
while (k < substr[i - 1].size() && substr[i - 1][k] < substr[i][j])
k++;
dp[i][j] =
max(dp[i][j - 1], dp[i - 1][k - 1] + (int)substr[i][j].size());
}
}
int ans = dp[n][substr[n].size() - 1];
if (ans < 0)
puts("-1");
else
printf("%d\n", ans);
return 0;
}