题解 P1666 【前缀单词】

· · 题解

蒟蒻觉得楼下说的还不完全清楚（但终究是dalao，该Orz还得Orz），在其之上做些补充。

我们预处理一个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]即可，当然最后还要算上空集哟。

参考代码：

#include<algorithm>
#include<iostream>
#include<string>
#define REP(i,a,b) for (register int i=(a);i<=(b);i++)
using namespace std;
const int N=61;
string a[N];
long long f[N][N],dp[N];
int n;
inline bool calc(int i,int j){
    if (a[i].size()>a[j].size())swap(i,j);
    return a[j].find(a[i])!=0;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    REP(i,1,n)cin>>a[i];
    sort(a+1,a+n+1);
    REP(i,1,n){
        dp[i]=1;
        REP(j,1,n)f[i][j]=calc(i,j);
    }
    REP(i,1,n)REP(j,i,n)dp[j]+=f[i][j]?dp[i]:0;
    long long ret=0;
    REP(i,1,n)ret+=dp[i];
    cout<<ret+1;
    return 0;
}