每日c/c++题 备战蓝桥杯（洛谷P1481 魔族密码 题解）

洛谷P1481 魔族密码 题解——动态规划破解最长前缀链标题

标题大意

给定N个蜜蜂族密码（字符串），要求找出最长的密码链。链中每个密码必须是前一个密码的前缀，且每个密码只能出现一次。例如密码"a"可以接"ab"、"abc"等，但"ba"不满足条件。
解题思绪

本题本质是求字符串数组中的最长前缀链长度，核心思绪是动态规划（DP）。通过维护一个dp数组，此中dp体现以第i个字符串末了的最长链长度。
状态定义

1. int dp[2005] = {0}; // dp[i]表示以ss[i]结尾的最长链长度

复制代码

状态转移

对于每个字符串ss，遍历它之前的所有字符串ss[j]：

• 当ss[j]是ss的前缀时，阐明可以将ss接在ss[j]之后
  
• 此时状态转移方程为：dp = max(dp, dp[j] + 1)
  

关键优化

使用字符串的find方法判断前缀关系：

1. if(ss[i].find(ss[j]) == 0) // 精确判断前缀

复制代码

该方法的时间复杂度为O(L)，此中L是字符串长度，比逐字符比较更高效。
代码解析

1. #include<bits/stdc++.h>
2. using namespace std;
4. int N;
5. string ss[2005] = {};
6. int dp[2005] = {0};
8. int main() {
9.     ios::sync_with_stdio(false); // 加速输入输出
10.     cin.tie(0); cout.tie(0);
11.    
12.     cin >> N;
13.     int ans = 0;
14.    
15.     for(int i = 1; i <= N; ++i) {
16.         cin >> ss[i];
17.         dp[i] = 1; // 每个字符串自身至少成链
18.         
19.         for(int j = 1; j < i; ++j) {
20.             // 精确前缀判断：ss[j]必须是ss[i]的开头
21.             if(ss[i].find(ss[j]) == 0) {
22.                 dp[i] = max(dp[i], dp[j] + 1);
23.             }
24.         }
25.         ans = max(ans, dp[i]); // 维护全局最优
26.     }
27.    
28.     cout << ans;
29.     return 0;
30. }

复制代码

执行流程

• 输入处置惩罚：使用快速IO优化处置惩罚大规模数据
  
• 初始化：每个字符串初始链长为1
  
• 双重循环：
  
  
  
  • 外层遍历每个字符串作为当前末了
    
  • 内层查抄所有前置字符串是否构成前缀关系
    
  
  
• 动态更新：通过比较所有大概的j < i的情况，维护最长链
  

复杂度分析

• 时间复杂度：O(N²L)，此中L为字符串均匀长度
  
• 空间复杂度：O(N)，仅需线性空间存储dp数组
  

对于N=2000的极限情况，总运算次数约为2000²×均匀长度。在C++的优化下可以通过本题，但仍有优化空间。
优化方向

1. 预处置惩罚前缀关系

建立前缀关系矩阵prefix[j]，预处置惩罚所有字符串对的前缀关系，将内层判断优化至O(1)。但需要O(N²)的额外空间。
2. 字典树优化

构建Trie树存储所有字符串，通过树的层级关系快速查找最长前缀链。可将时间复杂度优化至O(NL)，适合处置惩罚更大规模的数据。
3. 排序预处置惩罚

按字符串长度升序排序，保证处置惩罚次序满足动态规划的最优子结构性子，大概减少无效比较次数。
示例演示

以样例输入：

1. 5
2. a
3. b
4. ab
5. ba
6. abc

复制代码

为例，处置惩罚流程如下：
字符串遍历过程dp值变化a初始化为1dp[1]=1b初始化为1dp[2]=1ab比较a(是前缀)→dp[3]=2dp[3]=2ba比较a(否)/b(否)→保持1dp[4]=1abc比较a(是前缀)→dp[5]=2比较ab(是前缀)→dp[5]=3dp[5]=3 最终输出最长链长度3（a→ab→abc）。
总结

本题是典型的动态规划应用场景，通过状态转移方程捕捉前缀关系的递推性子。关键点在于：

• 精确明白前缀关系的定义
  
• 合理设计状态转移方程
  
• 选择高效的字符串前缀判断方法
  

此类标题在生物信息学（基因序列分析）、输入法词库优化等领域有实际应用代价。明白其思想有助于办理更复杂的字符串序列标题。