动态规划之-----单调递增最长子序列（nyoj17）

单调递增最长子序列

时间限制：3000 ms | 内存限制：65535 KB 难度：4 描述 求一个字符串的最长递增子序列的长度

如：dabdbf最长递增子序列就是abdf，长度为4 输入第一行一个整数0<n<20,表示有n个字符串要处理

随后的n行，每行有一个字符串，该字符串的长度不会超过10000输出输出字符串的最长递增子序列的长度样例输入

3aaaababcabklmncdefg

样例输出

137

单调递增最长子序列其实是最长公共子序列的一种变形，我们可以理解为一个字符串与其排序后的字符串求最长公共子序列。求最长公共子序列见：动态规划之——最长公共子序列

经典的常规解法：（原串与有序串求最长公共子序列）

#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;#define INF 10005char a[INF];char b[INF];short c[INF][INF];int main(){int t;scanf("%d", &t);while(t--){memset(c, 0, sizeof(c));scanf("%s", a+1);strcpy(b+1, a+1);int n = strlen(a+1);sort(b+1, b+n+1);for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){if(a[i]==b[j]&&b[j]!=b[j-1]) c[i][j] = c[i-1][j-1] + 1;else if(c[i-1][j]>=c[i][j-1]) c[i][j] = c[i-1][j];else c[i][j] = c[i][j-1];}}printf("%d\n", c[n][n]);}return 0;}

这种解法的问题在于，字符串的长度过大，二维表存储数据消耗空间过大，会爆内存。而另一个问题是：我们必须要排序吗？不排序hi否可以解决呢？

#include <stdio.h>#include <string.h>int main(){int t;scanf("%d", &t);while(t--){char s[10005]={0};int dp[10005]={0};scanf("%s", s);int l = strlen(s), max=0;for(int i=0; i<l; i++){for(int j=0; j<i; j++)if(s[j]<s[i] && dp[i]<dp[j]) dp[i]=dp[j];dp[i]++;if(max<dp[i]) max=dp[i];}printf("%d\n", max);}return 0;}

至此，AC，时间、空间复杂度都有了改善