题意：

就是现在给出m个串，每个串都有一个权值，现在你要找到一个长度不超过n的字符串，

其中之前的m个串每出现一次就算一次那个字符串的权值，

求能找到的最大权值的字符串，如果存在多个解，输出最短的字典序最小的串。

当最大全权值为0时输出空串。

输入最多100个子串，权值为不超过100的正整数。

每个子串长度至少为1，不超过10, n <= 50

 

如果不考虑方案输出，这题就变得相当简单了。

dp【i】【j】表示走到长度为 i 的时候 ，到AC自动机 j 这个节点所获得的最大权值和。

我一开始的做法是在dp的过程中获得那个最优方案。

最后死活过不去，就换了一种超级暴力的写法。

将所有情况保存下来，去一个个找字典序最小的方案。

 

1 #include 
      
         2 #include 
       

Q; 75 fail[root] = root; 76 for (int i = 0; i < 26; i++) 77 if (next[root][i] == -1) next[root][i] = root; 78 else { 79 fail[next[root][i]] = root; 80 Q.push(next[root][i]); 81 } 82 while (!Q.empty()) { 83 int now = Q.front(); 84 Q.pop(); 85 End[now] += End[fail[now]]; 86 for (int i = 0; i < 26; i++) 87 if (next[now][i] == -1) next[now][i] = next[fail[now]][i]; 88 else { 89 fail[next[now][i]] = next[fail[now]][i]; 90 Q.push(next[now][i]); 91 } 92 } 93 } 94 95 void debug() { 96 for (int i = 0; i < cnt; i++) { 97 printf("id = %3d,fail = %3d,end = %3d,chi = [", i, fail[i], End[i]); 98 for (int j = 0; j < 26; j++) printf("%2d", next[i][j]); 99 printf("]\n");100 }101 }102 } ac;103 104 int dp[55][1010];105 string path[55][1010];106 107 int main() {108 // FIN;109 int T;110 sf(T);111 while (T--) {112 sff(n, m);113 for (int i = 0; i < m; ++i) scanf("%s", str[i]);114 for (int i = 0; i < m; i++) sf(cost[i]);115 ac.init();116 for (int i = 0; i < m; ++i) ac.insert(str[i], cost[i]);117 ac.build();118 mem(dp, -1);119 for (int i = 0; i <= n; i++)120 for (int j = 0; j < ac.cnt; j++)121 path[i][j] = "";122 int ans = 0, num1 = 0, num2 = 0;123 dp[0][0] = 0;124 for (int i = 0; i < n; ++i) {125 for (int j = 0; j < ac.cnt; ++j) {126 if (dp[i][j] == -1) continue;127 for (int k = 0; k < 26; ++k) {128 int idx = ac.next[j][k];129 if (dp[i + 1][idx] < dp[i][j] + ac.End[idx]) {130 dp[i + 1][idx] = dp[i][j] + ac.End[idx];131 path[i + 1][idx] = path[i][j] + char(k + 'a');132 } else if (dp[i + 1][idx] == dp[i][j] + ac.End[idx] &&133 path[i + 1][idx] > path[i][j] + char(k + 'a')) {134 //fuck(path[i][j]);135 path[i + 1][idx] = path[i][j] + char(k + 'a');136 // fuck(path[i][j]);137 138 }139 }140 }141 }142 for (int i = 1; i <= n; i++) {143 for (int j = 0; j < ac.cnt; ++j) {144 if (ans < dp[i][j]) {145 ans = dp[i][j], num1 = i, num2 = j;146 } else if (ans == dp[i][j]&&path[num1][num2] > path[i][j] && path[num1][num2].size()>=path[i][j].size()) {147 num1 = i, num2 = j;148 }149 }150 }151 // printf("%d\n", ans);152 cout << path[num1][num2] << endl;153 }154 return 0;155 }