题目描述
求一个字符串的最长递增子序列的长度
如:dabdbf最长递增子序列就是abdf,长度为4
输入
第一行一个整数0<n<20,表示有n个字符串要处理
随后的n行,每行有一个字符串,该字符串的长度不会超过10000
输出
输出字符串的最长递增子序列的长度
样例输入
3 aaa ababc abklmncdefg
样例输出
1 3 7
提示
来源
NYOJ:http://acm.wydtang.top/problem/show/1113
模板如下:
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define mm(a) memset(a,0,sizeof(a))
int dp[10001],Max;
int LIS()
{
Max = 0;
string a;
cin>>a;
mm(dp);
for(int i = 0; i < a.size(); i++)
{
dp[i] = 1;
for(int j = 0; j < i; j++)
if(a[i] > a[j])
dp[i]=max(dp[i],dp[j]+1);
Max=max(Max,dp[i]);
}
return Max;
}
int main()
{
int N;
//freopen("C:\\Users\\nuoyanli\\Desktop\\acm.txt","r",stdin);
cin>>N;
while(N--)
cout<<LIS()<<endl;
return 0;
}