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

71 7 3 5 9 4 8Sample Output
4
题目大意：就是让你求最长的不下降子序列
题目分析：很简单的一道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; }