单调递增最长子序列

发布时间:2016-12-10 11:15:48 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"单调递增最长子序列",主要涉及到单调递增最长子序列方面的内容,对于单调递增最长子序列感兴趣的同学可以参考一下。

单调递增最长子序列 题目:http://acm.nyist.net/JudgeOnline/problem.php?pid=17 时间限制:3000 ms  |  内存限制:65535 KB 难度:4 描述 求一个字符串的最长递增子序列的长度 如:dabdbf最长递增子序列就是abdf,长度为4 输入 第一行一个整数0<n<20,表示有n个字符串要处理 随后的n行,每行有一个字符串,该字符串的长度不会超过10000 输出 输出字符串的最长递增子序列的长度 样例输入 3 aaa ababc abklmncdefg 样例输出 1 3 7 /* 单调递增最长子序列 时间限制:3000 ms | 内存限制:65535 KB 难度:4 描述 求一个字符串的最长递增子序列的长度 如:dabdbf最长递增子序列就是abdf,长度为4 输入 第一行一个整数0<n<20,表示有n个字符串要处理 随后的n行,每行有一个字符串,该字符串的长度不会超过10000 输出 输出字符串的最长递增子序列的长度 样例输入 3 aaa ababc abklmncdefg样例输出 1 3 7来源 经典题目 */ #include <iostream> #include <string> using namespace std; void LIS(const string& str) { int *arr=new int[str.length()]; for ( int i=0 ; i<str.length() ; ++i ){ arr[i]=1; } int maxLen=1; for ( int i=1 ; i<str.length() ; ++i ){ int temp=1; for ( int j=0 ; j<i ; ++j ){ int temp=str[i]>str[j] ? (arr[j]+1):arr[i]; arr[i]=arr[i]<temp ? temp:arr[i]; } maxLen= maxLen>arr[i] ? maxLen:arr[i]; } cout<<maxLen<<endl; delete []arr; } int main() { int num; string str; cin>>num; while (num--){ cin>>str; LIS(str); } return 0; }

上一篇:python之sqlite3使用详解
下一篇:UVA 152 Tree's a Crowd 一堆树 检索水题+暴力

相关文章

相关评论