LuoGuP1970花匠
简化题意 $:$
给定一个序列,求最长的波浪子序列.
单峰的意思是存在一个 $v_i$ 使得 $v_i > v_{i-1},v_i > v_{i+1}$ 且 $1$ 到 ${i-1}$ 单调,$i+1$ 到 $n$ 也单调(单调性相反).
令 $f_{i,0/1}$ 表示前 $i$ 个数字中,形状是 $\lor$ 或者 $\land$ 的最长长度.
每次比较当前元素和上一个元素的大小,考虑继承即可.
1 |
|
My Coding Life.
简化题意 $:$
给定一个序列,求最长的波浪子序列.
单峰的意思是存在一个 $v_i$ 使得 $v_i > v_{i-1},v_i > v_{i+1}$ 且 $1$ 到 ${i-1}$ 单调,$i+1$ 到 $n$ 也单调(单调性相反).
令 $f_{i,0/1}$ 表示前 $i$ 个数字中,形状是 $\lor$ 或者 $\land$ 的最长长度.
每次比较当前元素和上一个元素的大小,考虑继承即可.
1 | #include <algorithm> |