[luoguP1666] 前缀单词（DP）

传送门

先把所有字符串按照字典序排序一下

会发现有字符串x和y（x再y前面，即字典序小），如果x不是y的前缀，那么在x前面不是x前缀的字符串也不是y的前缀

这样就可以DP了

f[i][j]表示前i个字符串中选j个，且第j个必须选字符串i。有多少种集合，

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 101 #define LL long long using namespace std; int n; string s[N]; bool b[N][N]; LL ans, f[N][N]; //f[i][j]表示1~i号里取j个，i号必须取的方案数 inline bool check(int x, int y) int main() printf("%lld\n", ans + 1); return 0; }

　　

上一篇：[luoguP2622] 关灯问题II（状压最短路）

下一篇：[luoguP1472] 奶牛家谱 Cow Pedigrees（DP）

---

DP