记录dp的设计。一开始设计的是f[i][j]表示最后一个选i，匹配到j的最大值，然而这样转移是\(n^2\)的，题目要求\(n*m\).设计成0，1背包，考虑第i个选择或者不选择即可。#include<bits/stdc++.h>usingnamespacestd;constintN=1e3+11;intf[N][6];intlef[N][6],val[N][6],to[N

https://codeforces.com/contest/2005/problem/C题意：n个长度为m的字符串，可以任意选取若干个字符串组合起来，然后从中选择narek5个字符拼凑字符串，拼凑成功加5分，如果字母是narek中的其中一个并且没有使用，则扣一分，求最大分数。思路：dp，维护一个长度为5的数组，依次考虑在当前字符串中以

原题链接：https://codeforces.com/contest/2005/problem/C看了教程发现都是用dp做的，在这里分享一个差不多的SPFA的思路（赛场上忘了Dijkstra不能有负边所以炸了）时间复杂度与dp同样是O(nm)形式化题意和翻译：有n个长度为m的字符串，你可以选择或不选择来拼接它们，但是不能更改字符串的