View Code
1
#include<iostream>
2
#include<cstdio>
3
#include<cstring>
4
#define
Max 10010
5
#define
max(a,b) (((a) > (b)) ? (a) : (b))
6
using
namespace
std;
7
char
ch[Max];
8
int
d[Max];
9
int
dp(
int
i)
10
{
11
int
k,ans=
1
;
12
if
(d[i]!=-
1
)
13
return
d[i];
14
for
(k=i-
1
;k>=
0
;k--)
15
{
16
if
(ch[i]>ch[k])
17
{
18
d[k]=dp(k);
19
ans=max(ans,d[k]+
1
);
20
}
21
}
22
return
d[k]=ans;
23
}
24
int
main()
25
{
26
int
n,len,ans,i;
27
scanf(
"
%d
"
,&n);
28
while
(n--)
29
{
30
ans=
0
;
31
scanf(
"
%s
"
,ch);
32
len=strlen(ch);
33
memset(d,-
1
,
sizeof
(d));
34
for
(i=
0
;i<len;i++)
35
{
36
ans=max(ans,dp(i));
37
}
38
printf(
"
%d\n
"
,ans);
39
}
40
return
0
;
41
}
描述求一个字符串的最长递增子序列的长度
如：dabdbf最长递增子序列就是abdf，长度为4
- 输入
-
第一行一个整数0<n<20,表示有n个字符串要处理
随后的n行，每行有一个字符串，该字符串的长度不会超过10000 - 输出
- 输出字符串的最长递增子序列的长度
- 样例输入
-
3 aaa ababc abklmncdefg - 样例输出
-
1 3 7
