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
?
- 輸入
-
第一行一個整數(shù)0<n<20,表示有n個字符串要處理
隨后的n行，每行有一個字符串，該字符串的長度不會超過10000 - 輸出
- 輸出字符串的最長遞增子序列的長度
- 樣例輸入
-
3 aaa ababc abklmncdefg - 樣例輸出
-
1 3 7
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
