1328: 【动态规划】单调递增最长子序列

1328: 【动态规划】单调递增最长子序列

时间限制: 1 Sec   内存限制: 128 MB

题目描述

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

输入

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

输出

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

样例输入 Copy

3

aaa

ababc

abklmncdefg

样例输出 Copy

1

3

7

经典的动态规划问题

fi表示取第i个字符时的最优解

则fi=max(fk+1)   k<i且第k个字符小于第i个字符

代码如下：

#include<bits/stdc++.h>

using namespace std;

int main(){

int n;scanf("%d",&n);

for(int i=1;i<=n;i++){

char ch[10005];

scanf("%s",ch);

int len=strlen(ch);

int ans[10005],maxx=1;;

for(int i=0;i<len;i++) ans[i]=1;

for(int i=1;i<len;i++)

for(int j=0;j<i;j++)

if(ch[j]<ch[i]){

ans[i]=max(ans[i],ans[j]+1);

maxx=max(maxx,ans[i]);

}

printf("%d\n",maxx);

}

return 0;

}