NYOJ 370 波动序列

发布时间:2016-12-11 10:33:06 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"NYOJ 370 波动序列",主要涉及到NYOJ 370 波动序列方面的内容,对于NYOJ 370 波动序列感兴趣的同学可以参考一下。

波动序列 时间限制:1000 ms  |  内存限制:65535 KB 难度:2 描述 有一个长度为N的整数序列,序列里面的数是两两不同的,现在要在里面找一个波动序列,这个序列越长越好。 比如有波动序列{a0,a1,a2…an-1},则a0 > a1 < a2 > a3 < … 输入第一行输入一个数T,代表有T个任务,T不大于50。 对于每个任务,输入格式为 N a0 a1 a2 … aN-1  其中N<=30000,测试数据保证序列的数两两不同。 输出对于每个任务,输出最长的波动序列长度 样例输入 4 5 1 2 3 4 5 5 5 4 3 2 1 5 5 1 4 2 3 5 2 4 1 3 5 样例输出 1 2 5 3 /*读完这个题,我的第一感觉是:这是个dp问题。如果用普通方法做,时间复杂度是O(n^2),会超时。 后来想了一下,只需要判断是递增或递减就行了,O(n)时间复杂度。 即:对于当前的点,1、如果要找递增序列:如果下一个点比当前的点大,序列长度加1,更新下一个点为当前点; 如果下一个点比当前点小,长度不变,同样更新下一个点为当前点,而且有利于找出递增序列 找递减序列的方法与找递增序列的方法一致。*/ #include<stdio.h> int a[30003]; int main() { int T,N,i,flag,len,now; scanf("%d",&T); while(T--) { scanf("%d",&N); for(i=0;i<N;i++) scanf("%d",&a[i]); now=a[0]; flag=1;/*flag=0表示要找递增序列,flag=1表示要找递减序列*/ len=1; for(i=1;i<N;i++) { if(!flag&&a[i]>now) { flag=1; len++; } else if(flag&&a[i]<now) { flag=0; len++; } now=a[i]; } printf("%d\n",len); } return 0; }

上一篇:C++指针数组和指向指针的指针
下一篇:unity3d事件函数整理,事件,回调函数,消息处理

相关文章

相关评论