传送门：点击打开链接
题意：告诉你m个字符串，每个字符串有一个权值。再告诉你n，要求新的字符串长度小于等于n，现在求总权值最大的最小字典序字符串是多少
思路：首先用AC自动机去把状态优化，然后列出dp方程，这些都是不难的，问题还在于打印路径上。由于要求字典序最小，但是实际上在AC自动机顺着插入的话，只能比较后缀，根本比较不了前缀，所以不是很好做。有的题解是插入字符串到AC自动机的时候就把它翻转，这样我就只需要比较后缀就行了，但是比较字符串到时候也需要从后向前去扫，说实话写起来也是很麻烦的。。
这时突然想起了我队友以前经常没事做拿string保存路径递归，，我当时总说这样容易爆内存和超时，但是今天实在想不出什么其他的好办法了，没想到尝试的用了一下string保存路径，不仅代码非常简单，而且效果意外的好，时间上也没有慢太多，感觉有时候这种奇葩思路还是挺不错的。
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;/*MX为总长度*/
const int MN = 100 + 5;
const int MX = 1200 + 5;
const int INF = 0x3f3f3f3f;
const int P = 26;int dp[MN][MX];
string dps[MN][MX];struct AC_machine {int rear, root;int Next[MX][P], Fail[MX], End[MX], ans[MN];void Init() {rear = 0;root = New();}int New() {End[rear] = 0;for(int i = 0; i < P; i++) {Next[rear][i] = -1;}return rear++;}void Add(const char *A, int val) {int now = root, n = strlen(A);for(int i = 0; i < n; i++) {int id = A[i] - 'a';if(Next[now][id] == -1) {Next[now][id] = New();}now = Next[now][id];}End[now] += val;}void Build() {queue<int>Q;Fail[root] = root;for(int i = 0; i < P; i++) {if(Next[root][i] == -1) {Next[root][i] = root;} else {Fail[Next[root][i]] = root;Q.push(Next[root][i]);}}while(!Q.empty()) {int u = Q.front(); Q.pop();End[u] += End[Fail[u]];for(int i = 0; i < P; i++) {if(Next[u][i] == -1) {Next[u][i] = Next[Fail[u]][i];} else {Fail[Next[u][i]] = Next[Fail[u]][i];Q.push(Next[u][i]);}}}}void Solve(int N) {memset(dp, -INF, sizeof(dp));dp[0][0] = 0; dps[0][0] = "";for(int i = 1; i <= N; i++) {for(int j = 0; j < rear; j++) {for(int k = 0; k < P; k++) {int nxt = Next[j][k];int L = dp[i - 1][j] + End[nxt], R = dp[i][nxt];if(L < 0) continue;if(L > R || (L == R && dps[i - 1][j] + (char)('a' + k) < dps[i][nxt])) {dp[i][nxt] = L;dps[i][nxt] = dps[i - 1][j] + (char)('a' + k);}}}}for(int i = 0; i <= N; i++) {ans[i] = 0;for(int j = 1; j < rear; j++) {if(dp[i][j] > dp[i][ans[i]] || (dp[i][j] == dp[i][ans[i]] && dps[i][j] < dps[i][ans[i]])) {ans[i] = j;}}}int len = N;for(int i = N - 1; i >= 0; i--) {if(dp[i][ans[i]] == dp[len][ans[len]]) {len = i;}}printf("%s\n", dps[len][ans[len]].c_str());}
} AC;char word[MX];
vector<string>S;int main() {int T, n, m; //FIN;scanf("%d", &T);while(T--) {AC.Init();S.clear();scanf("%d%d", &n, &m);for(int i = 1; i <= m; i++) {scanf("%s", word);S.push_back(string(word));}for(int i = 0; i < m; i++) {int val;scanf("%d", &val);AC.Add(S[i].c_str(), val);}AC.Build();AC.Solve(n);}return 0;
}