nyoj 17 单调递增最长子序列（dp---记忆化搜索||穷举|| nlogn算法）

我不是女神ヾ 2024-02-17 20:50 28阅读 0赞

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

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

难度： 4

描述

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

输入

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

输出

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

样例输入

3
    aaa
    ababc
    abklmncdefg

样例输出

1
    3
    7

分析：动态规划思想，记忆化搜索 （508ms跑完）

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=10000+10;
    int d[maxn];
    char s[maxn];
    int len;
    
    int dp(int i){
    	int& cur=d[i];
    	if(cur>0)return cur;
    	cur=1;
    	for(int j=i+1;j<len;j++){
    		if(s[j]>s[i]){
    			cur=max(cur,dp(j)+1);
    		}
    	} 
    	return cur;
    }
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%s",s);
    		
    		len=strlen(s);
    		memset(d,0,sizeof(d));
    		int max1=0;
    		for(int i=0;i<len;i++){
    			max1=max(max1,dp(i));
    		}
    		printf("%d\n",max1);
    	}
    	return 0;
    }

解法二：穷举 （312ms跑完）

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=10000+10;
    char s[maxn];
    int dp[maxn];
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%s",s);
    		dp[0]=1;
    		int max1=1;
    		int len=strlen(s);
    		for(int i=1;i<len;i++){
    			dp[i]=1;
    			for(int j=0;j<i;j++){
    				if(s[i]>s[j]){
    					if(dp[i]<dp[j]+1){
    						dp[i]=dp[j]+1;
    						max1=max(max1,dp[i]);
    					}
    				}
    			}
    		}
    		printf("%d\n",max1);
    	}
    	return 0;
    }

解法3、nlogn算法 （如果对此算法不太了解，可以网上找相关资料） （4ms跑完）

AC代码：

#include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn=10000+10;
    char a[maxn];
    char B[maxn];   //保存的是长度为len时的最小末尾 
    
    int binary_search(int len,int i){
    	int first=1,last=len;
    	while(first<last){
    		int mid=first+(last-first)/2;
    		if(B[mid]>=a[i])last=mid;
    		else first=mid+1;
    	}
    	return first;
    }
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%s",a);
    		int l=strlen(a);
    		
    		B[1]=a[0];
    		int len=1;
    		for(int i=1;i<l;i++){
    			if(a[i]>B[len]){
    				B[++len]=a[i];
    			}
    			else {
    				int j=binary_search(len,i);
    				B[j]=a[i];
    			}
    		}
    		printf("%d\n",len);
    	}
    	return 0;
    }