nyoj 214-单调递增子序列(二) (演算法,PS:普通的动态规划要超时)
2023-09-11 14:21:11 时间
214-单调递增子序列(二)
内存限制:64MB
时间限制:1000ms
Special Judge: No
accepted:11
submit:35
题目描述:
给定一整型数列{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型整数)!
输出描述:
对于每组测试数据输出整形数列的最长递增子序列的长度,每个输出占一行。
样例输入:
7 1 9 10 5 11 2 13 2 2 -1
样例输出:
5
1
分析:
1、如果给的串本身是升序的,就直接加入进来temp[]串中
2、否则的话我们要找到第一个大于等于该值的位置,并改变该位置的值(使最终组成的temp[]串ASCⅡ码之和最小)
核心代码:
1 while(m --) 2 { 3 scanf("%d", &v); 4 if(temp[cnt] < v) 5 { 6 temp[++cnt] = v; 7 continue; 8 } 9 for(int i = 0; i <= cnt; ++ i) 10 { 11 if(temp[i] >= v) 12 { 13 temp[i] = v; 14 break; 15 } 16 } 17 }
C/C++代码实现(AC):
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <cstdio> 5 #include <cmath> 6 #include <stack> 7 #include <map> 8 #include <queue> 9 #include <set> 10 11 using namespace std; 12 const int MAXN = 100010; 13 14 int main() 15 { 16 17 int t, A[MAXN], temp[MAXN], cnt; 18 while(~scanf("%d", &t)) 19 { 20 cnt = 0; 21 memset(A, 0, sizeof(A)); 22 memset(temp, 0, sizeof(temp)); 23 scanf("%d", &A[0]); 24 temp[cnt] = A[0]; 25 for(int i = 1; i < t; ++ i) 26 { 27 scanf("%d", &A[i]); 28 if(temp[cnt] < A[i]) 29 { 30 temp[++cnt] = A[i]; 31 continue; 32 } 33 for(int j = 0; j <= cnt; ++ j) 34 if(A[i] <= temp[j]) 35 { 36 temp[j] = A[i]; 37 break; 38 } 39 40 } 41 printf("%d\n", cnt + 1); 42 } 43 return 0; 44 }
C/C++代码(TLE)<动态规划>:
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <cstdio> 5 #include <cmath> 6 #include <stack> 7 #include <map> 8 #include <queue> 9 #include <set> 10 11 using namespace std; 12 const int MAXN = 100010; 13 14 int main() 15 { 16 17 int t, A[MAXN], dp[MAXN], cnt; 18 while(~scanf("%d", &t)) 19 { 20 cnt = 0; 21 memset(A, 0, sizeof(A)); 22 memset(dp, 0, sizeof(dp)); 23 for(int i = 0; i < t; ++ i) 24 { 25 scanf("%d", &A[i]); 26 dp[i] = 1; 27 for(int j = 0; j < i; ++ j) 28 if(A[i] > A[j]) 29 dp[i] = max(dp[i], dp[j] + 1); 30 cnt = max(cnt, dp[i]); 31 } 32 printf("%d\n", cnt); 33 } 34 return 0; 35 }
相关文章
- 求解最长递增子序列长度|动态规划+二分查找:CC++实现
- Qt每3秒把程序最前显示一次,只是调整Z序列
- Java实现 LeetCode 392 判断子序列
- Java实现 LeetCode 105 从前序与中序遍历序列构造二叉树
- 分布式系统中的RPC请求经常出现乱序的情况 写一个算法来将一个乱序的序列保序输出
- Lintcode--010(最长上升子序列)
- 动态规划之最长公共子序列
- Leetcode.1359 有效的快递序列数目
- LeetCode-940. 不同的子序列 II【字符串,动态规划】
- 华为OD机试 - 非严格递增连续数字序列
- 通过展开序列ISTA(SISTA)算法创建的递归神经网络(RNN)(Matlab代码实现)
- numpy 中np.max--求序列的最大值和np.maximum--X和Y逐位进行比较,选择最大值
- 【关于时间序列的ML】项目 5 :用机器学习预测天气
- 594. 最长和谐子序列-快速排序
- Leetcode 594. 最长和谐子序列(已解决)
- 【数字信号处理】周期序列 ( 周期序列示例 2 | 模拟信号周期 | 数字信号周期 | 在 a 个模拟信号周期内采集 b 个数字信号采样 )
- [LeetCode] 300. 最长上升子序列 ☆☆☆(动态规划 二分)
- leetcode 300. 最长递增子序列 js 动态规划实现
- 碱基序列的儿子最长上涨
- 动态规划精讲(一)LC最长公共子序列
- VL35-状态机,非重叠的序列检测,设计一个状态机,检测序列10111.
- 【Leetcode刷题Python】1143. 最长公共子序列
- 试题 算法训练 摆动序列
- 动态规划05~不会吧,不会吧。还有人没把子序列和子串搞明白呀?