P1481 魔族密码

题目链接P1481 魔族密码 - 洛谷思路典型的dp题目首先如何判断两个单词组成词链首先后面的一定要比前边的长其次就是要满足前缀这个条件并不是子字符串这里用compare函数compare是“比较两段字符串”返回三个值之一0 相等 0 左边小 0 左边大它有三种用法这个题用到的是第二种。三个参数的形式a.compare(pos, len, b)读作把a从pos开始、取len个字符跟b比。dp思路dp[i]是前i个单词组成的最长词链转移就是对于第i个单词检索其前面所有的单词若满足条件就把这个单词接到后面也就是1最后综合比较哪种情况最大同时题目数据顺序不一定是有序的需要再进行排序以确认dp方向代码#includebits/stdc.h using namespace std; int main() { int n,ans 1; cin n; vectorstring arr(n); vectorint 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; }