memorial ;monument; statue与sculpture 这英语用谐音怎么读

不看样例我还以为走错考场了呢你确定这不是英语六级阅读理解?(还好我有Google翻译

给你 n 个字符串从中找一个最长子序列,要求该序列每一个字符串的最后一个字符囷后一个字符串的第一个字符相等并且,整个序列的第一个字符和最后一个字符相等

序列的长度为其中所有字符串的长度之和

看n的大小2e5,基本上死了暴力那条心(暴力大致要O(n2))
虽然我还是作死来了一发果然TLE
那对于这种求子序列的题目,其实应该有点感觉是dp,但dp嘚主要问题是如何寻找状态转移方程,如何确定每个维度的含义
如果直接让dp数组表示合法状态(即,符合题目要求的序列)那么将無法完成转移,因为合法状态可能要从非法状态转移而来(序列首尾字符不相等)所以我们将退让一步,让dp保留"最长"这个属性而在dp结束后筛查"合法状态",以保证状态的顺利转移

如此定义:dp[i][j] 代表首字符为 i ,尾字符为 j 的子序列的最大长度
此时放宽了要求(首位字符不一萣相等)

用rmap记录目前的首字符r,是否在尾部出现过以保证能连接

用集合s记录以r字符结尾的子序列的首字符

特别鸣谢:吴老板提供的技术支持

我要回帖

更多关于 statue 的文章

 

随机推荐