洛谷1666 前缀单词

首先预处理一下两个单词 $s[i],s[j]$ 是否安全并记录在 $can[i][j]$ 中，用 $f[i]$ 代表包含第 $i$ 个单词的安全组有多少个。

枚举每一个小于当前单词的单词，如果他们俩安全，那么当前单词和 枚举单词所在的安全组成员 在一起也一定是安全的，所以加上答案即可。

$$f[j]= \begin{cases} f[j] \\ f[j]+f[i] , can[i][j] \& s[i]<=s[j] \end{cases}$$

所以很显然需要事先排序，还有虽然数据看起来小但答案其实很大，要开long long。

string s[55];
bool can[55][55];
ll n,f[55],ans=1ll;

inline bool check(int x,int y)
{
    int len=min(s[y].length(),s[x].length());
    for (int i=0;i<len;i++)
    {
        if (s[x][i]==s[y][i]) continue;
        return 1;
    }
    return 0;
}

int main()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>s[i],f[i]=1;
    sort(s+1,s+n+1);
    for (int i=n;i;i--)
        for (int j=1;j<i;j++)
            can[i][j]=can[j][i]=check(i,j);
    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++)
            f[j]+=can[i][j] ? f[i] : 0;
    for (int i=1;i<=n;i++) ans+=f[i];
    printf("%lld",ans);
    return 0;
}