【OI练习】数列

【OI练习】数列

Description

　　给定一串整数数列，求出所有的递增和递减子序列的数目，如数列7，2，6，9，8，3，5，2，1可分为（7，2），（2，6，9），（9，8，3），（3，5），（5，2，1）5个子序列，答案就是5，我们称2，9，3，5为转折元素。

Input

　　输入第一行为n(n <= 100)；第二行为n个数；

Output

　　输出所有的递增和递减子序列的数目

　　 Sample Input

9 7 2 6 9 8 3 5 2 1

Sample Output

5

题目分析

一开始尝试直接计算递增子序列和递减子序列数目，但一直调试不对。 再次分析题目发现：本题中的子序列，是连续的。为此，我们只需算出递增递减的转折次数+1即可。 即有： walk*(a[i]-a[i-1])>0代表未发生转折 walk*(a[i]-a[i-1])<0代表发生转折 walk为当前点的前两项之差 #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; int main(){ int a[101]; int n; cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; } int up=0,down=0,walk=0; walk=a[1]-a[0]; if (walk>0) up +=1; else down +=1; for (int i=2;i<n;i++) { if (walk*(a[i]-a[i-1])<0) { walk=a[i]-a[i-1]; if (walk>0) up +=1; else down +=1; } } printf("%d",up+down); }