单调递增最长子序列【DP】

单调递增最长子序列

时间限制： 3000 ms  |  内存限制： 65535 KB 难度： 4 描述 求一个字符串的最长递增子序列的长度 如：dabdbf最长递增子序列就是abdf，长度为4 输入 第一行一个整数0<n<20,表示有n个字符串要处理 随后的n行，每行有一个字符串，该字符串的长度不会超过10000 输出 输出字符串的最长递增子序列的长度 样例输入 3 aaa ababc abklmncdefg 样例输出 1 3 7 来源 经典题目 上传者 iphxer 代码 #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #include<stack> #include<vector> #define inf 0x3f3f3f #define M 10000+10 using namespace std; char str[M]; int dp[M]; int main() { int n; scanf("%d",&n); while(n--) { scanf("%s",str); memset(dp,0,sizeof(dp)); int maxx=-inf; for(int i=0;i<strlen(str);i++) { dp[i]=1; for(int l=0;l<i;l++) { if(str[l]<str[i]&&dp[i]<dp[l]+1) dp[i]=dp[l]+1; } if(dp[i]>maxx) maxx=dp[i]; } printf("%d\n",maxx); } return 0; }