传送门
先把所有字符串按照字典序排序一下
会发现有字符串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（状压最短路）
下一篇：[luoguP1494] 岳麓山上打水 && [luoguP2744] [USACO5.3]量取牛奶Milk Measuring
DP
