Id	1094
Title	临界波
Tags	implementation dp
Brief solution	注意起始位置是一个波峰或波谷。dp的状态是以当前位置作为波峰（波谷）的最优解。状态转移时，只需要找到前一个波谷（波峰）即可（更前的不会更优）。由于数n不超过1000，所以状态转移直接用O(n)的也是可行的。当然O(1)的状态转移也是可以的。