nyoj 17 单调递增最长子序列

描述

求一个字符串的最长递增子序列的长度
如：dabdbf最长递增子序列就是abdf，长度为4

输入

第一行一个整数0<n<20,表示有n个字符串要处理
随后的n行，每行有一个字符串，该字符串的长度不会超过10000

输出

输出字符串的最长递增子序列的长度

样例输入

3
aaa
ababc
abklmncdefg

样例输出

1
3
7

AC代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 #define N 10006
 6 char s[N];
 7 int dp[N];
 8 int main()
 9 {
10     int t;
11     scanf("%d",&t);
12     while(t--){
13        scanf("%s",s);
14        int len = strlen(s);
15        dp[0]=1;
16        for(int i=1;i<len;i++){
17           int max_ = 0;
18           for(int j=0;j<i;j++){
19               if(s[i]>s[j] && max_<dp[j]){
20                  max_ = dp[j];
21               }
22           }
23           dp[i] = max_+1;
24        }
25        int ans = 0;
26        for(int i=0;i<len;i++){
27            ans = max(ans,dp[i]);
28        }
29        printf("%d
",ans);
30     }
31     return 0;
32 }