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

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

题目大意

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

解题思路

本题本质是求字符串数组中的最长前缀链长度，核心思路是动态规划（DP）。通过维护一个dp数组，其中dp[i]表示以第i个字符串结尾的最长链长度。

状态定义

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

状态转移

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

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

关键优化

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

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

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

代码解析

#include
using namespace std;
int N;
string ss[2005] = {};
int dp[2005] = {0};
int main() {
    ios::sync_with_stdio(false); // 加速输入输出
    cin.tie(0); cout.tie(0);
    
    cin >> N;
    int ans = 0;
    
    for(int i = 1; i 
        cin > ss[i];
        dp[i] = 1; // 每个字符串自身至少成链
        
        for(int j = 1; j