[ACM_NYOJ_17]单调递增最长子序列
杰拉斯 | 时间:2013-05-04, Sat | 7,949 views编程算法
单调递增最长子序列
时间限制:3000 ms | 内存限制:65535 KB
描述
求一个字符串的最长递增子序列的长度
如:dabdbf最长递增子序列就是abdf,长度为4
输入
第一行一个整数0 随后的n行,每行有一个字符串,该字符串的长度不会超过10000 输出字符串的最长递增子序列的长度 思路类似《Longest Ordered Subsequence(最长有序子序列)》 代码如下: 如需转载请注明出处:杰拉斯的博客输出
样例输入
3
aaa
ababc
abklmncdefg
样例输出
1
3
7
来源
#include<iostream>
#include<string>
using namespace std;
int main(){
int t;
string s;
cin >> t;
while(t--){
cin >> s;
int ans = 0, f[10000];
for(int i = 0, len = s.length(); i < len; ++i){
int max = 0;
for(int j = 0; j < i; ++j){
if(s[j] < s[i] && max < f[j]){
max = f[j];
}
}
if((f[i] = max + 1) > ans){
ans = f[i];
}
}
cout << ans << "\n";
}
return 0;
}
相关文章
当前暂无评论 »