1134 最長遞增子序列(暴力寫的)

可以用二分寫...

基準時間限制：1 秒 空間限制：131072 KB 分值: 0 難度：基礎題

 收藏

 關注

給出長度為N的數組，找出這個數組的最長遞增子序列。(遞增子序列是指，子序列的元素是遞增的）

例如：5 1 6 8 2 4 5 10，最長遞增子序列是1 2 4 5 10。

Input

第1行：1個數N，N為序列的長度(2 <= N <= 50000)
第2 - N + 1行：每行1個數，對應序列的元素(-10^9 <= S[i] <= 10^9)      

Output

輸出最長遞增子序列的長度。      

Input示例

8
5
1
6
8
2
4
5
10      

Output示例

5      

相關問題

最長遞增子序列 V2 

160

最長遞增子序列的數量 

break  很是巧妙...

代碼:

1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstring>
 4 #include <string>
 5 #include <algorithm>
 6 #include <queue>
 7 #include <stack>
 8 #include <map>
 9 #include <set>
10 #include <vector>
11 #include <iostream>
12 using namespace std;
13 #define for0(i, n) for(int i=0; i<(n); ++i)
14 #define for1(i,a,n) for(int i=(a);i<=(n);++i)
15 #define for2(i,a,n) for(int i=(a);i<(n);++i)
16 #define for3(i,a,n) for(int i=(a);i>=(n);--i)
17 #define for4(i,a,n) for(int i=(a);i>(n);--i)
18 #define CC(i,a) memset(i,a,sizeof(i))
19 #define LL long long
20 #define MOD 1000000007
21 #define INF 0x3f3f3f3f
22 #define MAX 50100
23 
24 int dp[MAX],num[MAX];
25 int n;
26 
27 int main()
28 {
29     scanf("%d",&n);
30     memset(dp,INF,sizeof(dp));
31     memset(num,INF,sizeof(num));
32     for(int i=0; i<n; i++)
33         scanf("%d",&dp[i]);
34     int path=0;
35     for(int i=0; i<n; i++){
36         for(int j=0; j<n; j++){
37             if(dp[i]<num[j]){
38                 num[j]=dp[i];
39                 if(path<j)
40                     path=j;
41                 break;
42             }
43         }
44     }
45     printf("%d\n",path+1);
46 }