NYOJ 17 单调递增最长子序列

偏执的太偏执、 2022-08-25 05:21 161阅读 0赞

## 单调递增最长子序列 ##

时间限制： 3000 ms | 内存限制： 65535 KB

难度： 4

描述

求一个字符串的最长递增子序列的长度  
如：dabdbf最长递增子序列就是abdf，长度为4

输入

第一行一个整数0<n<20,表示有n个字符串要处理  
随后的n行，每行有一个字符串，该字符串的长度不会超过10000

输出

输出字符串的最长递增子序列的长度

样例输入

3
    aaa
    ababc
    abklmncdefg

样例输出

1
    3
    7

思路：经典动态规划问题。

#include <stdio.h>
    #include <string.h>
    
    char s[10010];
    int dp[10010];
    
    void LIS()
    {
    	int i,j;
    	int len = strlen(s);
    	memset(dp,0,sizeof(dp));
    	for (i=0; i<len; i++)
    	{
    		dp[i] = 1;//设置初始最大长度为1
    		for (j=0; j<i; j++)
    		{
    			if (s[i] > s[j])
    			{//如果当前字符有比前面的字符大时，即满足递增条件。
    				if (dp[i] < dp[j] + 1)
    				{//更新最大值，即可以求得满足条件的从0~i的的最大长度。
    					dp[i] = dp[j] + 1;
    				}
    			}
    		}
    	}
    }
    
    int main()
    {
    	int  n;
    	scanf("%d",&n);
    	while (n--)
    	{
    		int i,len;
    		int maxlen = 0;
    		scanf("%s",s);
    		LIS();
    		len = strlen(s);
    		for (i=0; i<len; i++)
    		{//选择一个最大长度即是单调递增最长子序列
    			if (maxlen < dp[i])
    			{
    				maxlen = dp[i];
    			}
    		}
    		printf("%d\n",maxlen);
    	}
    	return 0;
    }

以下转自[http://www.cnblogs.com/mycapple/archive/2012/08/22/2651453.html][http_www.cnblogs.com_mycapple_archive_2012_08_22_2651453.html]

地址：[http://acm.nyist.net/JudgeOnline/problem.php?pid=17][http_acm.nyist.net_JudgeOnline_problem.php_pid_17]

题目分析：同NYOJ 79 拦截导弹

先解释下什么叫子序列。若a序列删去其中若干个元素后与b序列完全相同，则称b是a的子序列。

我们假定存在一个单调序列\{An\}（以递增序列为例)，现在在其后面添加一个元素a(n+1)，有两种情况：

1.a(n+1)>a(n) 。此时，a(n+1)可以添加到An序列的尾部，形成一个新的单调序列，并且此序列长度大于之前An的长度；

2.a(n+1)<=a(n)。此时，a(n+1）当然不可以添加到An序列的尾部。

经过分析，我们可以得出这样的结论：一个单调序列与其后面元素的关系仅与此序列的末尾元素有关。

如此，便有了此题如下的dp解法：

建立一个一维数组dp\[ \]，用dp\[i\]保存长度为i的单调子序列的末尾元素的值，用top保存单调子序列的最大长度。

初始top=1，dp\[1\]=a1；

然后，我们从前向后遍历序列An（i : 2~n)。显然，我们会遇到两种情况：

1.a\[i\] > dp\[top\]。此时，我们把a\[i\]加入到长度为top的单调序列中，这时序列长度为top+1，top值也跟着更新，即dp\[++top\] = a\[i\]；

2.a\[i\]<=dp\[top\]。此时，a\[i\]不能加入长度为top的单调序列，那它应该加入长度为多少的序列呢？

做法是，从后向前遍历dp\[ \] (j: top-1~1)，直到满足条件 a\[i\] > dp\[j\]，此时，类似于步骤1，我们可以把a\[i\]加入到长度为j的单调序列中，这时此序列长度为j+1，

我们将dp\[j+1\]的值更新为a\[i\]。可是，为什么要更新它呢？

因为a\[i\]一定小于dp\[j+1\]。为什么呢？如果a\[i\]不小于dp\[j+1\]，我们找到的j就应该是j+1而不是j。那么，我们为什么要保留把dp\[j+1\]的最小值呢？

因为对于相同长度的单调递增序列来说，末尾元素的值越小，其后元素加入此序列的可能性越大，也就是说，我们这样做，是为了防止丢失最优解。

思路1：

这题其实是跟导弹拦截一样的，因为还有个加强版，所以把这个跟加强版一起贴上来。经典动态规划题,以后的动态规划很多都是从这个衍生出来的

一 最长递增子序列问题的描述

设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>，其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。

假设L是字符串长度，i是字符串下标，f(i)代表当前以S\[i\]为首字母的字符串最大长度， 递推公式：f(i)=max(f(i+1),f(i+2),...,f(L-1),f(L))+1；用一个int dp\[i\]数组保存当前的f(i)值，可想而知最后 \*max\_element(dp,dp+L) 便得到了答案。  
二 算法：动态规划法:O(n^2)

设f(i)表示L中以ai为末元素的最长递增子序列的长度。则有如下的递推方程：

f(i)=max(f(i+1),f(i+2),...,f(L-1),f(L))+1；用一个int dp\[i\]数组保存当前的f(i)值，可想而知最后 \*max\_element(dp,dp+L) 便得到了答案  
这个递推方程的意思是，在求以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为末元素的递增子序列。一般在解决问题的时候都是用到动态规划，所以就贴出代码了。主要用这个。。。。。。

代码如下：

#include<stdio.h>//**O（n^2）
    #include<string.h>
    int main()
    {
        char str[10001];
        int s,len,i,j,dp[10001],max;
        scanf("%d",&s);
        while(s--)
        {
            max=0;
            scanf("%s",str);
            len=strlen(str);
            for(i=0;i<=len-1;i++)
            {
                dp[i]=1;//**dp[i]的最小值为1**//
            }
            for(i=len-2;i>=0;i--)     //这点表示不太懂，正研究着。。。
            {
                for(j=i+1;j<=len-1;j++)
                {
                    if(str[i]<str[j]&&dp[i]<dp[j]+1) //最长递增子序列则a[j]>a[i],而最长递减子序列则a[j]<a[i]...好好体会。。。
                    {
                        dp[i]=dp[j]+1;//**更新dp[i]的值**//
                    }
                }
            }
            for(i=0;i<=len-1;i++)
            {
                if(dp[i]>max)
                {
                    max=dp[i];
                }
            }
            printf("%d\n",max);
        }
    }

思路2：

LIS算法(最长上升子序列)

LIS（Longest Increasing Subsequence）最长上升（不下降）子序列，有两种算法复杂度为O(n\*logn)和O(n^2)。在上述算法中，若使用朴素的顺序查找在D1..Dlen查找，由于共有O(n)个元素需要计算，每次计算时的复杂度是O(n)，则整个算法的时间复杂度为O(n^2)，与原来算法相比没有任何进步。但是由于D的特点(2)，在D中查找时，可以使用二分查找高效地完成，则整个算法时间复杂度下降为O(nlogn)，有了非常显著的提高。需要注意的是，D在算法结束后记录的并不是一个符合题意的最长上升子序列！算法还可以扩展到整个最长子序列系列问题。

有两种算法复杂度为O(n\*logn)和O(n^2)

借鉴代码如下：

//LIS算法实现
    #include <stdio.h>
    #include<string.h>
    char str[10001];
    int main()
    {
        int T,i,j;int len,ans;
        scanf("%d",&T);
        while(T--)
        {
            memset(str,0,sizeof(str));
            scanf("%s%*c",str);
            len=strlen(str);
            ans=0;
            for(i=0;i<len;i++)
            {
                for(j=0;j<ans;j++)
                    if(str[j]>=str[i]) 
                    { 
                        str[j]=str[i]; 
                        break;
                    }
                if(j==ans)
                {
                    str[j]=str[i];
                    ans++;
                }
            }
            printf("%d\n",ans);
        }
        return 0;
    }

在贴一个比较优秀的代码。

#include<stdio.h>   
    int length(char * s)  
    {  
        int len[128] = {0}, i, t;  
        for(; *s != '\0' && (t = len[*s - 1] + 1); s++)  
        for(i = *s; i < 128 && len[i] < t; len[i++] = t);  
        return len[127];  
    }  
    int main()  
    {  
        int n;  
        char s[10001];  
        for(scanf("%d\n", &n); n--;)  
        printf("%d\n", length(gets(s)));  
        return 0;  
    }

[http_www.cnblogs.com_mycapple_archive_2012_08_22_2651453.html]: http://www.cnblogs.com/mycapple/archive/2012/08/22/2651453.html
[http_acm.nyist.net_JudgeOnline_problem.php_pid_17]: http://acm.nyist.net/JudgeOnline/problem.php?pid=17