天天看點

UVA 10534-Wavio Sequence(LIS)

題目大意:Wavio序列是關于整數的序列,有這樣的性質:

1.長度為奇數,L=2*n+1

2.前n+1項嚴格遞增

3.後n+1項嚴格遞減

4.相鄰的兩個數不相等

給出n個數的序列,求出其中最長的Wavio子序列的長度。

依次對每個元素求以它為結束的最長上升子序列和以它為開始的最長下降子序列,b[i]為以i為最後一個元素的最長上升子序列,c[i]為以i為第一個元素的最長下降子序列,最後周遊每一個數,答案為max { min { b[i],c[i] } }。

代碼是初學時寫的,很難看。。到時補個好的貼上。。