思路

这道题是一道动态规划的题目。我们首先考虑预处理出一个数组，来存放两两单词是否安全。之后我们再利用这个信息来进行DP。而有一个值得注意的要点是：我们在动态规划时要消除后效性，否则就会出现错误。在本题中，我们需要对字符串进行排序，因为排序后不安全的单词只存在于在第\(i\)个单词的前面，这样我们用一维\(dp\)即可。考虑方程：\(dp[j] += dp[i], j \in [i, n], possible[i][j] == true\)即可。

代码

// P1666.cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 60;
string dict[maxn];
long long n, dp[maxn], current;
bool possible[maxn][maxn];
bool isPrefix(string a, string b)
{
    if (b.length() > a.length())
        swap(a, b);
    return (a.find(b) == 0);
}
int main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        cin >> dict[i];
    sort(dict + 1, dict + n + 1);
    for (int i = 1; i <= n; i++)
    {
        dp[i] = 1;
        for (int j = 1; j <= n; j++)
            if (!isPrefix(dict[i], dict[j]))
                possible[i][j] = possible[j][i] = true;
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            if (possible[i][j])
                dp[j] += dp[i];
    for (int i = 1; i <= n; i++)
        ans += dp[i];
    printf("%lld", ans + 1);
    return 0;
}