单调递增最长子序列
时间限制：3000 ms | 内存限制：65535 KB
难度：4
描述
求一个字符串的最长递增子序列的长度
如：dabdbf最长递增子序列就是abdf，长度为4
输入
第一行一个整数0<n<20,表示有n个字符串要处理
随后的n行，每行有一个字符串，该字符串的长度不会超过10000
输出
输出字符串的最长递增子序列的长度
样例输入
3
aaa
ababc
abklmncdefg样例输出
1
3
7
在求以ai为末元素的最长递增子序列时，找到所有序号在L前面且小于ai的元素aj，即j<i且aj<ai。如果这样的元素存在，那么对所有aj,都有一个以aj为末元素的最长递增子序列的长度f(j)，把其中最大的f(j)选出来，那么f(i)就等于最大的f(j)加上1，即以ai为末元素的最长递增子序列，等于以使f(j)最大的那个aj为末元素的递增子序列最末再加上ai；如果这样的元素不存在，那么ai自身构成一个长度为1的以ai为末元素的递增子序列。
//AC
#include<stdio.h>
#include<string.h>
#define N 10001
int dp(char str[],int n)
{
int i,j;int max;int d[N];
for(i=0;i<N;i++)
d[i]=1;
for(i=n-2;i>=0;i--)
for(j=i+1;j<=n-1;j++)
if(str[j]>str[i]&&d[i]<d[j]+1)
d[i]=d[j]+1;//不能是d[i]++,因为要保证递增
max=d[0];
for(i=1;i<n;i++)
{
if(max<d[i])
max=d[i];
}
return max;
}
int main()
{
int i,j,len;int T,ans;
char str[N];
scanf("%d",&T);
for(i=1;i<=T;i++)
{
scanf("%s",str);
//memset(str,0,sizeof(str));
len=strlen(str);
ans=dp(str,len);
printf("%d\n",ans);
}
return 0;
}
//wa，必须把d[N]开在函数内并初始化为1，
#include<stdio.h>
#include<string.h>
#define N 10001
int d[N];
char str[N];
int dp(char str[],int n)
{
int i,j;int max;
for(i=n-2;i>=0;i--)
for(j=i+1;j<=n-1;j++)
if(str[j]>str[i]&&d[i]<d[j]+1)
d[i]=d[j]+1;//不能是d[i]++,因为要保证递增
max=d[0];
for(i=1;i<n;i++)
{
if(max<d[i])
max=d[i];
}
return max;
}
int main()
{
int i,j,len;int T,ans;
scanf("%d",&T);
for(i=0;i<N;i++)
d[i]=1;
for(i=1;i<=T;i++)
{
scanf("%s",str);
//memset(str,0,sizeof(str));
len=strlen(str);
ans=dp(str,len);
printf("%d\n",ans);
}
return 0;
}
