单调递增最长子序列
http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=17
时间限制： 3000 ms | 内存限制：65535 KB
难度： 4
- 描述
- 求一个字符串的最长递增子序列的长度 如：dabdbf最长递增子序列就是abdf，长度为4
- 输入
- 第一行一个整数0<n<20,表示有n个字符串要处理 随后的n行，每行有一个字符串，该字符串的长度不会超过10000 输出
- 输出字符串的最长递增子序列的长度 样例输入
-
3aaaababcabklmncdefg
样例输出 -
137
方法一： #include
#include using namespace std;string str;int dp[10005];int main(){ int t; cin >> t; while(t--){ cin >> str; for(int i = 0; i < str.length(); i++){ dp[i] = 1; } int max = 0; for(int i = 0; i < str.length(); i++){ for(int j = 0; j < i; j++){ if(str[i] > str[j] && dp[j] + 1 > dp[i]){ dp[i] = dp[j] + 1; } } if(max < dp[i]){ max = dp[i]; } } cout << max << endl; } return 0;} 方法二：（for循环查找或二分查找：所求序列不一定正确，但长度正确）#include #include using namespace std;string str;int main(){ int t; cin >> t; while(t--){ int leng = 0; char ans[10005]; cin >> str; ans[0] = str[0]; for(int i = 1; i < str.length(); i++){ if(str[i] > ans[leng]){ ans[++leng] = str[i]; } else{// for(int j = 0; j <= leng; j++){ //在ans中查找第一个比str[i]大或等的字母(即最小的最大值)，将其替换掉 // if(str[i] <= ans[j]){ //可以用二分查找 // ans[j] = str[i];// break;// }// } int x = lower_bound(ans, ans + leng, str[i]) - ans; //STL： 二分： t = lower_bound(s,s+top,m)-s; 返回值第一个大于等于m的数的地址，s是一个数组，top是查 //找长度，要减 s 得第一个大于等于m 的数的下标 //http://blog.csdn.net/zhongkeli/article/details/6883288 ans[x] = str[i]; } } cout << leng + 1 << endl; } return 0;}