洛谷1970 花匠

简要题意

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

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

简要题解

算法1:DP+线段树优化

设$up[i]$表示到$i$结尾,这一个数比上一个数大的最长长度。

设$down[i]$表示到$i$结尾,这一个数比上一个数小的最长长度。

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

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

代码略。

算法2:贪心

XJB乱贪心。

首先第一个一定选。

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

接下来每一个:如果和前一个方向不一样就选,否则用它替代前一个(这样更容易找到方向不一样的。)

就行了。

没错就这么简单,$O(n)$。

代码同样略。(虽然我写了)

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×