转载请注明出处：優YoU http://user.qzone.qq.com/289065406/blog/1300023619
提示：
动态规划，求LIS最大不下降子序列
O(n^2)和O(n*logn)算法都能完美AC
不懂的就去看看LIS的概念就会做了
我把两种算法都贴出来：
1 //Memory Time
2 //228K 16MS
3
4 //O(n^2)算法
5 #include<iostream>
6 using namespace std;
7
8 int main(int i,int j)
9 {
10 int n;
11 while(cin>>n)
12 {
13 int* sq=new int[n];
14 int* dp=new int[n]; //dp[i]表示以第i个位置为终点的最长不下降序列的长度
15
16 for(i=0;i<n;i++)
17 cin>>sq[i];
18
19 int max_length=0;
20 for(i=0;i<n;i++)
21 {
22 dp[i]=1; //初始化dp[0]=1,其他最小值为1
23 for(j=0;j<i;j++)
24 if(sq[j]<sq[i] && dp[i]<dp[j]+1)
25 dp[i]=dp[j]+1;
26
27 if(max_length<dp[i])
28 max_length=dp[i];
29 }
30 cout<<max_length<<endl;
31
32 delete sq,dp;
33 }
34 return 0;
35 }
===========华丽的分割线=============
1 //Memory Time
2 //224K 0MS
3
4 //O(n*logn)算法
5 #include<iostream>
6 using namespace std;
7 const int inf=10001;
8
9 int binary_search(int ord[],int digit,int length) //二分法搜索digit，若str中存在digit，返回其下标
10 { //若不存在，返回str中比digit小的最大那个数的（下标+1）
11 int left=0,right=length;
12 int mid;
13 while(right!=left)
14 {
15 mid=(left+right)/2;
16 if(digit==ord[mid])
17 return mid;
18 else if(digit<ord[mid])
19 right=mid;
20 else
21 left=mid+1;
22 }
23 return left;
24 }
25
26 int main(int i,int j)
27 {
28 int n;
29 while(cin>>n)
30 {
31 int* sq=new int[n+1];
32 int* ord=new int[n+1]; //对于dp[]的每一个取值k，ord[k]记录满足dp[i]=k的所有sq[i]中的最小值，即ord[k]=min{sq[i]} (dp[i]=k)
33
34 for(i=1;i<=n;i++)
35 cin>>sq[i];
36
37 int max_length=0;
38 ord[0]=-1; //下界无穷小
39 int len=1; //ord的长度
40 for(i=1;i<=n;i++)
41 {
42 ord[len]=inf; //上界无穷大,指针len总是指向ord最后一个元素的后一位
43 j=binary_search(ord,sq[i],len);
44 if(j==len) //sq[i]大于ord最大（最后）的元素
45 len++;
46 ord[j]=sq[i];
47 }
48 cout<<len-1<<endl; //len要减去ord[0]的长度1
49
50 delete sq,ord;
51 }
52 return 0;
53 }