Vijos1028. 魔族密码

Vijos1028. 魔族密码2015-09-26题目概述

风之子刚走进他的考场, 就……

花花: 当当当当~~偶是魅力女皇——花花！！^^（华丽出场, 礼炮, 鲜花）

风之子: 我呕……（杀死人的眼神）快说题目！否则……-_-###

花花: ……咦~~好冷~~我们现在要解决的是魔族的密码问题（自我陶醉: 搞不好魔族里面还会有人用密码给我和菜虫写情书咧, 哦活活, 当然是给我的比较多拉*^_^*）. 魔族现在使用一种新型的密码系统. 每一个密码都是一个给定的仅包含小写字母的英文单词表, 每个单词至少包含1个字母, 至多75个字母. 如果在一个由一个词或多个词组成的表中, 除了最后一个以外, 每个单词都被其后的一个单词所包含, 即前一个单词是后一个单词的前缀, 则称词表为一个词链. 例如下面单词组成了一个词链:

int

integer

但下面的单词不组成词链:

integer

intern

现在你要做的就是在一个给定的单词表中取出一些词, 组成最长的词链, 就是包含单词数最多的词链. 将它的单词数统计出来, 就得到密码了.

风之子: 密码就是最长词链所包括的单词数啊……

输入

第一行为单词表中的单词数N（1<=N<=2000）, 下面每一行有一个单词, 按字典顺序排列, 中间没有重复的单词.

输出

在第一行输出密码

解题思路

这道题是最长不下降子序列. 比如一个序列{ 3, 5, 6, 2, 8 }, 则最长不下降子序列为{ 3, 5, 6, 8 }.

那么如何求这个序列呢？这个问题可以转换为, 求f（i） = max{ f（j） } + 1. （其中f（j）为前j个数中的最长不下降子序列）

我们需要一个数组length[], 记录1~n个元素的最长不下降子序列的值.

对于第i个元素, length[i] = max{ length[j] } + 1（ 0 <= j < i ）, 且满足 words[j] 是 words[i] 的子序列（words[]是用于保存单词链的数组）.

遇到的问题

难得这么顺利, 没有遇到什么问题, 连O（n^2）的代码也能AC.

源代码

#include <iostream>#include <fstream>#include <string> bool compareString（const std::string& str1, const std::string& str2） {size_t i = 0, j = 0;for （ ; i < str1.size（） && j < str2.size（）; ++ i, ++ j ） {if （ str1[i] ！= str2[j] ） {break;}}return （i == str1.size（） || j == str2.size（））;} int main（） {using std::cin;// std::ifstream cin;// cin.open（"input.txt"）; const int SIZE = 2000;int n = 0;std::string words[SIZE]; // Inputcin >> n;for （ int i = 0; i < n; ++ i ） {cin >> words[i];} // Processingint length[SIZE] = {0};for （ int i = 0; i < n; ++ i ） {length[i] = 1;for （ int j = 0; j < i; ++ j ） {if （ compareString（words[i], words[j]） && length[j] <= length[i]） {length[i] = length[j] + 1;}}} // Outputint maxLength = 0;for （ int i = 0; i < n; ++ i ） {if （ length[i] > maxLength ） {maxLength = length[i];}}std::cout << maxLength << std::endl; return 0;}