poj 2533 Longest Ordered Subsequence （最長不下降子序列）

2019-11-08 01:43:36

字體：大中小

來源：轉載

供稿：網友

A numeric sequence of a_i is ordered if a₁ < a₂ < ... < a_N. Let the subsequence of the given numeric sequence ( a₁, a₂, ..., a_N) be any sequence ( a_i₁, a_i₂, ..., a_{i_K}), where 1 <= i₁ < i₂ < ... < i_K <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8). Your PRogram, when given the numeric sequence, must find the length of its longest ordered subsequence.InputThe first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000OutputOutput file must contain a single integer - the length of the longest ordered subsequence of the given sequence.Sample Input

71 7 3 5 9 4 8Sample Output4
題目大意：就是讓你求最長的不下降子序列
題目分析：很簡單的一道dp，只是為了鞏固一下自己對dp的理解，所以又做了一下，狀態轉移方程就是
  if（a[j]>a[i]）  dp[j]=max（dp[i]+1，dp[j]）；
  不過這道題目還有二分的寫法，好像是省時間的，我
#include <cstdio>#include <cstring>#include <iostream>using namespace std;#define maxn 10005int dp[maxn],a[maxn];int main(){	int n;	while((scanf("%d",&n))!=EOF){		memset(dp,0,sizeof(dp));		memset(a,0,sizeof(a));		int ans=0;		for(int i=1;i<=n;i++)			scanf("%d",&a[i]);	    for(int i=1;i<=n;i++){	    	for(int j=i+1;j<=n;j++){	    		if(a[j]>a[i]&&dp[i]+1>dp[j])	    		  dp[j]=dp[i]+1;			}			if(dp[i]>ans)			 ans=dp[i];		}		printf("%d/n",ans+1);	}	return 0;} 然后，還有一種是省時間的二分法求最長不下降子序列方法。
就是開一個數組用來存儲當前最長長度為k的不下降子序列的末尾元素，每次讀入數據，如果大于f【k】，則更新k，k++，否則就把這個數據放在大于這個元素的最小f【i】。然后查找方法用二分，所以省時間。
#include <cstdio>#include <cstring>#include <iostream>using namespace std;#define maxn 1005int f[maxn];int search(int a,int l,int r){	int m;	while(l<=r){		m=(l+r)/2;		if(f[m] == a){		 l=m;		 return l;			}		  		else if(f[m] > a)			r=m-1;		else l=m+1;	}	return l;//確保返回的是大于a的最小值 }int main(){	int n,t,a;	while((scanf("%d",&n))!=EOF){		memset(f,0,sizeof(f));	t=0;		for(int i=1;i<=n;i++){					scanf("%d",&a);			int k=search(a,1,t);			if(k<=t)  f[k]=a;			else {			  t=t+1;			  f[t]=a;			}		}		 printf("%d/n",t);	}	return 0; }