759
NYOJ370-波動序列
波動序列
時間限製：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
來源
GDUT校賽
AC代碼:
#include<stdio.h>
int a[30010];
int main()
{
int i,n,m,sum,count,x;
scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
sum=1;
for(i=0;i<m;i++)
{
scanf("%d",&a[i]);
}
x=1;count=a[0];
for(i=1;i<m;i++)
{
if(x==1&&count>a[i])
{sum++;x=2;}
else
if(x==2&&count<a[i])
{sum++;x=1;}
count=a[i];
}
printf("%d\n",sum);
}
return 0;
}
最後更新：2017-04-03 16:49:17