题目描述

一组单词是安全的，当且仅当不存在一个单词是另一个单词的前缀，这样才能保证数据不容易被误解。现在你手上有一个单词集合，你需要计算有多少个子集是安全的。

注意空集永远是安全的。
输入格式

第一行一个数
表示集合的大小，以下n行。每行一个由

构成的字符串。
输出格式

安全子集的个数。
样例

输入 #1

3
hello
hell
hi

输出 #1

6

首先：设dp[i]表示前i个集合以i结尾的集合数

核心代码：dp[i] = dp[j]（1<=j<i且a[i]与a[j]不互为前缀）+ 1 (原谅我不会求和)

但是问题在于与j不互为前缀的单词不一定与i不互为前缀，这里直接从小到大排序就可以解决

引理：把这些字符串排序后，对于任意一组j<i且他们不互为前缀，则对于任意一组k<j且他们不互为前缀，则k与i不互为前缀。
证明：将三个字符串设为k,j,i，i=k+s,则k<j<k+s,可知j包含k，与题设矛盾。

这里排序后的n个数没有变，求解空间是一样的。若不排序，则答案一定会偏大(有些决策会被计算，实际并不符合)，而不会偏小。其实排序只是利用引理让决策集合有序。

亮代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
string s[55];
int n,a[55][55];
long long dp[55];
int check(int x,int y){if(s[x].length()>s[y].length())swap(x,y);for(int i=0;i<s[x].length();++i){if(s[x][i]!=s[y][i]) return 1;}return 0;
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){cin>>s[i];dp[i]=1;}sort(s+1,s+n+1);long long ans=1;for(int i=2;i<=n;i++)for(int j=i-1;j>=0;j--)if(check(i,j))dp[i]+=dp[j];for(int i=1;i<=n;i++)ans+=dp[i];printf("%lld",ans);return 0;
}