P1666 前缀单词

题目描述

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

注意空集永远是安全的。

输入输出格式

输入格式：

 

第一行一个数n，表示集合的大小，以下n行。每行一个由’a’……’z’构成的字符串。

【数据规模】

对30%的数据，满足1≤n≤10;

对于100%的数据，满足1≤n≤50;字符串长度≤50，没有两个字符串是完全相同的。

 

输出格式：

 

安全子集的个数。

 

输入输出样例

输入样例#1： 

3hellohellhi

输出样例#1： 

6

 

枚举小状态来找状态转移方程

 

洛谷题解

我们预处理一个f[i][j]表示第i个单词与第j个单词是否能共存，

然后考虑一个dp[i]表示在前i个单词中，必须包含第i个单词的子集个数，首先dp[i]=1（只包含自己一个元素的一个子集方案数）

那么如果前面存在一个j<i，并且f[i][j]=1（即i与j可以共存），那么j所有的子集方案数加上一个i元素就形成了对应新的方案，那么状态就由j转移到i了，最后，直接累计dp[1....n]即可，当然最后还要算上空集哟。

参考代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #define REP(i,a,b) for (register int i=(a);i<=(b);i++) 5 using namespace std; 6 const int N=61; 7 string a[N]; 8 long long f[N][N],dp[N]; 9 int n;10 inline bool calc(int i,int j){11     if (a[i].size()>a[j].size())swap(i,j);12     return a[j].find(a[i])!=0;13 }14 int main(){15     ios::sync_with_stdio(false);16     cin>>n;17     REP(i,1,n)cin>>a[i];18     sort(a+1,a+n+1);19     REP(i,1,n){20         dp[i]=1;21         REP(j,1,n)f[i][j]=calc(i,j);22     }23     REP(i,1,n)REP(j,i,n)dp[j]+=f[i][j]?dp[i]:0;24     long long ret=0;25     REP(i,1,n)ret+=dp[i];26     cout<