XXXX年突然有外星人造访但大家语訁不通,不过科学家们经过研究发现外星人用26个英文字母组成的单词中最长不降子序列的长度来表述数字且英文字母的排列顺序不同,現给出其排列顺序再给出外星人说的每个数字(其实是每个英文单词,用空格隔开)翻译出外星人所说的数字(连续输出,最后加回車)
(因为是最长不降子序列,所以数字中没有0也就是说外星人的数字是>=1的数字)
该题被某人形容为恶心。。
其实也不是很难做吧?感谢!
|
|
根据第一行的字母表得到每个字母的权值
然后用O(n2)O(n2)的dp来求最长不降子序列
fifi表示以第i个字母结尾的最长不降子序列