P1481 魔族密码

题目链接：

P1481 魔族密码 - 洛谷

思路：

典型的dp题目

首先，如何判断两个单词组成词链？

首先后面的一定要比前边的长

其次就是要满足前缀这个条件（并不是子字符串）

这里用compare函数：

compare是“比较两段字符串”，返回三个值之一：

0 相等 < 0 左边小 > 0 左边大

它有三种用法，这个题用到的是第二种。

三个参数的形式

a.compare(pos, len, b)

读作：

把a从pos开始、取len个字符，跟b比。

dp思路：

dp[i]是前i个单词组成的最长词链；

转移：就是对于第i个单词，检索其前面所有的单词，若满足条件，就把这个单词接到后面，也就是+1；最后综合比较哪种情况最大；

同时题目数据顺序不一定是有序的，需要再进行排序，以确认dp方向：

代码：

#include<bits/stdc++.h> using namespace std; int main() { int n,ans = 1; cin >> n; vector<string> arr(n); vector<int> dp(n,1); for(int i = 0;i < n;i++) cin >> arr[i]; sort(arr.begin(),arr.end()); for(int i = 0;i < n;i++) for(int j = 0;j < i;j++) { if(arr[i].size() > arr[j].size() && arr[i].compare(0,arr[j].size(),arr[j]) == 0) { dp[i] = max(dp[i],dp[j] + 1); ans = max(ans,dp[i]); } } cout << ans; return 0; }