首页 > 代码库 > HDU 5532 Almost Sorted Array（最长不下降或不上升子序列）
HDU 5532 Almost Sorted Array（最长不下降或不上升子序列）
题目戳这
题目：给你一个序列，问你，这个序列只减少一个元素，减少之后是否为不上升序列或者不下降序列。
思路：直接对序列求最长不下降和不上升子序列，如果这个子序列的长度为n-1或者n的话，就符合题目条件。
最长不下降子序列和最长不上升子序列：这里使用数据结构的方法求最长不上升（下降）子序列的长度。就是另外构造一个数组 f[] ，这个数组表示的意思是：f [ i ] 表示的是长度为 i 的子序列的最小（最大值），因为，同样长度的子序列，最后一个数字最小或最大的时候，更方便往后面放数字。这个时候可能会说就算我的这个数字足够小或者足够大，如果位置不对，那么以他为结尾的序列长度也不能是最长的。至于这个问题，其实，我们更新的是 f[] ，每次我们都从头到尾地扫 f[] ，更新这个数组，就不会出现那个问题了。
1 #include<stdio.h> 2 #include<iostream> 3 #include<string.h> 4 #include<math.h> 5 #include<algorithm> 6 #include<vector> 7 #include<string> 8 #include<queue> 9 #include<map>10 #include<stack>11 #include<set>12 #define ll long long13 #define maxn 10001014 #define PI acos(-1.0) //圆周率15 const int mod=1e9+7;16 using namespace std;17 int num[maxn];18 int f[maxn];19 int n;20 int main()21 {22 int T;23 scanf("%d",&T);24 while(T--)25 {26 memset(f,0,sizeof(f));27 memset(num,0,sizeof(num));28 29 scanf("%d",&n);30 for(int i=0;i<n;i++) scanf("%d",&num[i]);31 32 int len=1;33 f[0]=num[0];34 for(int i=1;i<n;i++)35 {36 if(num[i]>=f[len-1]) f[len++]=num[i];37 else38 {39 int cnt=upper_bound(f,f+len,num[i])-f;40 f[cnt]=num[i];41 }42 }43 44 if(len==n-1||len==n)45 {46 printf("YES\n");47 continue;48 }49 50 len=1;51 memset(f,0,sizeof(f));52 f[0]=num[n-1];53 for(int i=n-2;i>=0;i--)54 {55 if(num[i]>=f[len-1]) f[len++]=num[i];56 else57 {58 int cnt=upper_bound(f,f+len,num[i])-f;59 f[cnt]=num[i];60 }61 }62 63 if(len==n-1||len==n) printf("YES\n");64 else printf("NO\n");65 }66 67 return 0;68 }
HDU 5532 Almost Sorted Array（最长不下降或不上升子序列）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。