NYOJ--单调递增最长子序列

电玩女神 2022-08-26 05:52 171阅读 0赞

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

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

难度： 4

描述

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

输入

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

输出

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

样例输入

3
    aaa
    ababc
    abklmncdefg

样例输出

1
    3
    7

解析：该题求单调最长子序列，与上篇博客中的最大子序列和是一种类型的题，利用动态规划的方法来求解，上篇中有详细的解释，DP[10001]中存放的是字符串的每个字符为结尾的最长子序列的长度，比如字符串str=“ababc”

置数组DP[i]=1，以字串中第二个字符b为结尾的字符串是b, ab 再判断单调str[i]>str[j]如果单调性成立，则DP[1]=DP[0]+1,反之DP[1]=1

当i=4此时str[i]='c'此时DP[0]=1 DP[1]=2 DP[2]=1 DP[3]=2

判断单调性,str[4]>str[0] 成立则DP[4]=DP[0]+1>DP[4]?DP[0]+1:DP[4]  这步是求当前最长的子序列

以此递推，就可以找到字符串中以每个字符为结尾时单调最长的子序列的长度保存到DP数组中去，这就是简单的动态规划问题

贴代码：

#include <iostream>
    #include <string>
    using std::endl;
    using std::cout;
    using std::cin;
    using std::string;
    int main()
    {
    	int DP[10001];
    	int n;
    	cin >> n;
    	while(n--)
    	{
    		string str;
    		cin >> str;
    		int maxlength = 1;
    		DP[0]=1;
    		for(int i=1 ; i<str.length(); ++i)
    		{
    			//循环的时候顺便对DP数组进行赋值
    			DP[i] = 1;
    			for(int j=0 ; j<i ; ++j)
    			{
    				//判断单调性
    				if(str[j] < str[i])
    				{
    					//求出当前以str[i]字符结尾的单调最长的长度，所以与先前计算的进行比较
    					DP[i] = DP[j] +1 > DP[i] ? DP[j]+1:DP[i];
    				}
    			}
    			if(DP[i] > maxlength)
    				maxlength = DP[i];
    		}
    		cout << maxlength << endl;
    	}
    	return 0;
    }