题意
给定 \(n\) 个字符串 \(s_1, s_2, ..., s_n\)。
你需要在其中选择一些字符串，按照顺序拼接。
在所有生成的长度为 \(k\) 的字符串中，选择字典序最小的一个。
\(n \le 2000, k \le 10 ^ 4, \sum |s_i| \le 10 ^ 6\)
Sol
考虑一个朴素的 dp。
设 \(f_{i, j}\) 表示前 \(i\) 个字符串，放到了前 \(j\) 个位置的最小的字符串。
这个 dp 的复杂度为 \(nk \times \sum |s_i|\)。
不难注意到一个事情，如果当前放的字符串 \(s_i\) 已经不是最优的字典序了，那么无论后面怎么放，此处放 \(s_i\) 都不可能成为最优方案。
考虑想的暴力一点：
设 \(f_{i, j, k}\) 表示用第 \(j\) 个字符串的第 \(k\) 位填在第 \(i\) 位，是否可以为当前字典序最小的方案，且合法。
先考虑简单的合法，每次新放一个字符串都需要判断放当前字符串是否可以组成长度为 \(k\) 的答案。
设 \(g_{i, j}\) 表示用第 \(j\) 个字符串填完前 \(i\) 位是否能合法。
显然：
\[\forall k \in [j + 1, n], g_{i, j} = g_{i, j} \vee g_{i + len_j, k} \]\(g_{i, j}\) 显然可以在 \(O(nk)\) 的时间求出。
考虑当前的最小字符。
注意到当前可以填的最小字符 \(s_{j, k}\) 满足：
\[\left\{ \begin{aligned} & \min_{j, k} s_{j, k + 1} , & & [f_{i - 1, j, k} = 1] \\ & \min_{j} s_{j, 1} , & & [\exists k, k < j, f_{i - 1, k, len_k} = 1] & \end{aligned} \right. \]注意到下面的式子和 \(g\) 类似，可以在 \(O(nk)\) 之内找出最小字符 \(c\)。
考虑上面的式子。
考虑直接把 \(j, k\) 两维暴力压成一维后用 \(\text{bitset}\) 维护。
二分当前的最小字符 \(c\)，考虑预处理 \(h_{i, j}\) 表示第 \(j\) 个位置存在字典序小于等于 \(i\) 字符。
那么一个很显然的事情，当前最小字符为 \(c\) 合法，当且仅当 (h[c] & (f[i - 1] << 1)) 的 \(\text{bitset}\) 存在 \(1\)。
考虑二分 \(c\)，复杂度：\(O(\frac{n \times \sum |s_i|}{\omega} \times \log 26)\)。
那么转移就很简单了。
\[\left\{ \begin{aligned} f_{i, j, k} \to f_{i + 1, j, k + 1}, & & s_{j, k + 1} = c \\ f_{i, j, len_j} \to f_{i + 1, k, 1}, & & s_{k, 1} = c, g_{i + 1, k} = 1 \\ \end{aligned} \right. \]实现细节较多。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <string>
#include <bitset>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
#endif
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
string read_() {
string ans;
char c = getchar();
while (c < 'a' || c > 'z') c = getchar();
while (c >= 'a' && c <= 'z') ans += c, c = getchar();
return ans;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
bool _stmer;
const int N = 2e3 + 5, M = 1e6 + 5, K = 1e4 + 5;
array <int, N> len, fir, sum;
array <bitset <N>, K> g, suf;
array <bitset <M>, 27> h;
array <bitset <M>, 2> f;
bitset <M> pre, vis;
bool check(int v, int c) { return (h[c] & (f[v] << 1)).count(); }
bool _edmer;
int main() {
cerr << (&_stmer - &_edmer) / 1024.0 / 1024.0 << "MB\n";
/* #ifdef cxqghzj */
/* freopen("_.txt", "r", stdin); */
/* #endif */
int n = read(), m = read();
string mp;
/* write(f[0].count()), puts("#"); */
for (int i = 1; i <= n; i++)
vis[fir[i] = mp.size()] = 1, mp += read_(), len[i] = (sum[i] = mp.size()) - fir[i];
for (int i = 1; i <= 26; i++)
for (int j = 0; j < (int)mp.size(); j++)
if (!vis[j])
h[i][j + 1] = (mp[j] <= ('a' + i - 1));
suf[m + 1][n + 1] = 1;
#define upd(x, y) (x = x | y)
for (int j = n; j; j--) {
for (int i = 1; i + len[j] - 1 <= m; i++)
upd(g[i][j], suf[i + len[j]][j + 1]);
for (int i = 1; i <= m + 1; i++) suf[i][j] = g[i][j] | suf[i][j + 1];
}
f[0][0] = 1, pre[1] = 1;
int v = 0;
string ans;
for (int i = 0; i < m; i++) {
int l = 1, r = 26;
for (int j = 1; j <= n; j++) {
if (pre[j] && g[i + 1][j]) r = min(r, mp[fir[j]] - 'a' + 1);
pre[j + 1] = f[v][sum[j]] | pre[j];
}
pre = 0;
while (l < r) {
int mid = (l + r) >> 1;
if (check(v, mid)) r = mid;
else l = mid + 1;
}
ans.push_back(r + 'a' - 1);
f[v ^ 1] = h[r] & (f[v] << 1);
bool flg = 0;
for (int j = 0; j <= n; j++) {
if (j && g[i + 1][j] && mp[fir[j]] <= r + 'a' - 1)
upd(f[v ^ 1][fir[j] + 1], flg);
flg |= f[v][sum[j]];
}
/* write(f[v ^ 1].count()), puts(""); */
v ^= 1;
}
printf("%s\n", ans.c_str());
return 0;
}