波动序列
序列 波动
2023-09-27 14:23:52 时间
1030: 波动序列
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 62 Solved: 29
Description
有一个长度为N的整数序列，序列里面的数是两两不同的，现在要在里面找一个波动序列，这个序列越长越好。
比如有波动序列{a0,a1,a2…an},则a0 > a1 < a2 > a3 < …
Input
第一行输入一个数T，代表有T个任务,T不大于50。
对于每个任务，输入格式为
N a0 a1 a2 … aN
其中N<=30000，测试数据保证序列的数两两不同。
Output
对于每个任务，输出最长的波动序列长度
Sample Input
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
Sample Output
1
2
5
3
HINT
思路：利用贪心思想，对于当前的点，若他的下一个需要是比他小的，那么如果对于下个点有两种情况
FROM：暑假训练第四场
1、 该点比他低，那么序列长度加一，更新当前点为现在的点
2、 该点比他高，那么序列长度不变，更新当前点为现在的点，那么该点升高了，有利于对下一个点的判断
代码：
#include<iostream>
#include<stdio.h>
using namespace std;
#define MAX 30000
int num[MAX+10];
int main(){
int n,m,i,now,ans,state;
scanf("%d",&n);
while(n--){
scanf("%d",&m);
for(i=0;i<m;i++)
scanf("%d",&num[i]);
now=num[0];ans=1;state=1;
for(i=1;i<m;i++){
if(now>num[i]&&state==1){
state=2;
ans++;
}
if(now<num[i]&&state==2){
state=1;
ans++;
}
now=num[i];
}
printf("%d\n",ans);
}
return 0;
}
FROM：暑假训练第四场