[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 i;
	for(i = 0; i < s[x].length(); i++)
		if(s[x][i] != s[y][i])
			return 0;
	return 1;
}

int main()
{
	int i, j, k;
	scanf("%d", &n);
	for(i = 1; i <= n; i++) cin >> s[i]; 
	sort(s + 1, s + n + 1);
	for(i = 1; i <= n; i++)
		for(j = 1; j < i; j++)
			b[j][i] = check(j, i);
	f[0][0] = 1;
	for(i = 1; i <= n; i++)
		for(j = 1; j <= i; j++)
		{
			for(k = 0; k < i; k++)
				if(!b[k][i])
					f[i][j] += f[k][j - 1];
			ans += f[i][j];
		}
	printf("%lld\n", ans + 1);
	return 0;
}