P1666 前缀单词

题目描述

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

注意空集永远是安全的。

输入输出格式

输入格式：

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

【数据规模】

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

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

输出格式：

安全子集的个数。

输入输出样例

输入样例#1：复制

3
hello
hell
hi

输出样例#1：复制

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

洛谷题解

我们预处理一个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<algorithm>
 2 #include<iostream>
 3 #include<string>
 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<<ret+1;
27     return 0;
28 }