洛谷1970 花匠

简要题意

给定一个序列，求最长波浪子序列。

波浪序列是指一个大一个小这样循环或一个小一个大这样循环。

简要题解

算法1：DP+线段树优化

设\(up[i]\)表示到\(i\)结尾，这一个数比上一个数大的最长长度。

设\(down[i]\)表示到\(i\)结尾，这一个数比上一个数小的最长长度。

可以很显然的发现\(O(n^2)\)的状态转移方程（略）

然后用线段树优化一发，复杂度变为\(O(n log 1000000)\)

代码略。

算法2：贪心

XJB乱贪心。

首先第一个一定选。

接着第二个只要和第一个不一样就选。

接下来每一个：如果和前一个方向不一样就选，否则用它替代前一个（这样更容易找到方向不一样的。）

就行了。

没错就这么简单，\(O(n)\)。

代码同样略。（虽然我写了）