首页 > 代码库 > NYOJ 214 单调递增子序列(二)
NYOJ 214 单调递增子序列(二)
单调递增子序列(二)
时间限制：1000 ms | 内存限制：65535 KB
难度：4
- 描述
给定一整型数列{a1,a2...,an}（0<n<=100000），找出单调递增最长子序列，并求出其长度。
如：1 9 10 5 11 2 13的最长单调递增子序列是1 9 10 11 13，长度为5。
- 输入
- 有多组测试数据（<=7）
每组测试数据的第一行是一个整数n表示序列中共有n个整数，随后的下一行里有n个整数，表示数列中的所有元素.每个整形数中间用空格间隔开（0<n<=100000）。
数据以EOF结束 。
输入数据保证合法（全为int型整数）！ - 输出
- 对于每组测试数据输出整形数列的最长递增子序列的长度，每个输出占一行。
- 样例输入
71 9 10 5 11 2 1322 -1
- 样例输出
51
解题：数据量大啊，o(n^2)方法不奏效啊！只有o(nlogn)算法了
先附上TLE代码吧
View Code1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <vector> 6 #include <climits> 7 #include <algorithm> 8 #include <cmath> 9 #define LL long long10 using namespace std;11 int d[100010],dp[100010];12 int main(){13 int n,i,j,ans;14 while(~scanf("%d",&n)){15 for(i = 1; i <= n; i++){16 scanf("%d",d+i);17 dp[i] = 1;18 }19 ans = 1;20 for(i = 2; i <= n; i++){21 for(j = i-1; j; j--){22 if(d[j] < d[i] && dp[i] < dp[j]+1) dp[i] = dp[j]+1;23 }24 if(dp[i] > ans) ans = dp[i];25 }26 printf("%d\n",ans);27 }28 return 0;29 }
好吧，上 AC 代码，O(nlogn)算法，精妙之处在于折半查找，速度很快的。噢最后那个top?top:1可以去掉的，秀逗了！损失4ms。
View Code1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <vector> 6 #include <climits> 7 #include <algorithm> 8 #include <cmath> 9 #define LL long long10 using namespace std;11 int stk[100010],top;12 void bsearch(int lt,int rt,int val) {13 int mid;14 while(lt <= rt) {15 mid = (lt+rt)>>1;16 if(val < stk[mid]) rt = mid-1;17 else lt = mid+1;18 }19 stk[lt] = val;20 }21 int main() {22 int n,i,temp;23 while(~scanf("%d",&n)) {24 top = 0;25 for(i = 1; i <= n; i++) {26 scanf("%d",&temp);27 if(!top || stk[top-1] < temp)28 stk[top++] = temp;29 else bsearch(0,top-1,temp);30 }31 printf("%d\n",top?top:1);32 }33 return 0;34 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。