// 2533 Longest Ordered Subsequence
#include <stdio.h>
#include <stdlib.h>

int lcs_length(int x[],int y[],int n);
int cmp (const void *a,const void *b); 
void copy(int src[],int dest[],int n);
/*
void qsort(int a[],int i,int j);
int findpivot(int a[],int i,int j);
int partition(int a[],int l,int r,int pivot);
void swap(int a[],int i,int j);
*/
int main()
{
	int a[1001],tmp[1001]; // 0 to 10000 
    int n;	// 1 <= N <= 1000
	int i;
    scanf("%d",&n);	
	for (i=0;i<n;i++) {			
		scanf("%d",&a[i]);			
	}   	    
	copy(a,tmp,n);
	qsort(tmp,n,sizeof(int),cmp); 
	printf("%d\n",lcs_length(a,tmp,n));
	return 0;
}

int lcs_length(int x[],int y[],int n) {	
	int i,j;
	int c[n+1][n+1];	
	for (i=1;i<=n;i++) 
		c[i][0] = 0;
	for (j=0;j<=n;j++) 
		c[0][j] = 0;
	for (i=1;i<=n;i++) {
		for (j=1;j<=n;j++) {
			if (x[i-1]==y[j-1]) {
				c[i][j] = c[i-1][j-1]+1; 				
			} else if (c[i-1][j] >= c[i][j-1]) {
				c[i][j] = c[i-1][j];				
			} else {
				c[i][j] = c[i][j-1];				
			}
		}
	}
	return c[n][n];
}

int cmp (const void *a,const void *b) 
{ 
	return *(int *)a - *(int *)b; 
} 

void copy(int src[],int dest[],int n)
{
	int i;
	for(i=0;i<n;i++) dest[i]=src[i];
}

• 简单的ＤＰ (57) yiyiyi4321 2005-12-23 08:21:21
  • acm.hnu.cn怎么开不出来…… (63) frkstyc 2005-12-23 08:39:47
    • http://acm.hnu.cn:8080/online/ 应该可以开的 :) (29) yiyiyi4321 2005-12-23 09:02:45
      • 原来不会自动跳转的…… (33) frkstyc 2005-12-23 09:11:29
        • 可以自动跳转的…… (0) yiyiyi4321 2005-12-23 09:17:56
          • .......... (0) frkstyc 2005-12-23 09:23:07
• Re:教科书上的做法，数组复制出来排序，再跟原来的求最大子序列长度，总是WA,谁能帮我看看啊！！ (1391) gsyagsy 2007-07-25 11:40:15