【动态规划】单调递增最长子序列
<center>
提交: 36 解决: 25
[提交][状态][讨论版] </center>
问题 D: 【动态规划】单调递增最长子序列
时间限制: 1 Sec 内存限制: 128 MB提交: 36 解决: 25
[提交][状态][讨论版] </center>
题目描述
求一个字符串的最长递增子序列的长度
如：dabdbf最长递增子序列就是abdf，长度为4
输入
第一行一个整数0<n<20,表示有n个字符串要处理
随后的n行，每行有一个字符串，该字符串的长度不会超过10000
输出
输出字符串的最长递增子序列的长度
样例输入
3
aaa
ababc
abklmncdefg
样例输出
1
3
7
解题思路：做了好几次的题，结果每次一看却想不起怎么做得来了。主要还是对动态规划的理解不透彻，不大清楚什么样的开一维数组，什么样的开二维数组。
再就是做题的时候独立思考太差，总是想看别人的解题过程。
解题参照：http://www.cnblogs.com/TWS-YIFEI/p/5592511.html
代码：
#include <cstdio> #include <iostream> #include <cstring> using namespace std; int main() { int n; char a[10001]; int len; int ans; int b; int sum[10001]; scanf("%d",&n); while(n--){ scanf("%s",a); len=strlen(a); for(int i=0;i<len;i++){ sum[i]=1; } for(int i=1;i<len;i++){ b=0; ans=0; for(int j=0;j<i;j++){ if(a[j]<a[i]){ ans=max(ans,sum[j]); b=1; } } if(b!=0){ sum[i]=ans+1; } } for(int i=0;i<len;i++){ ans=max(ans,sum[i]); } printf("%d\n",ans); } } /************************************************************** Problem: 1328 User: zz13 Language: C++ Result: 正确 Time:0 ms Memory:1696 kb ****************************************************************/
