読者です 読者をやめる 読者になる 読者になる

ctyl's problem solving

競技プログラミングが主な話題です。

yukicoder No.209 Longest Mountain Subsequence

DP★3.3ヶ月位前にも一度挑戦していて,その時は自分の方針のアラが探せず出来ずじまいだったが,今回は一発でACできた.

方針:{S_{i-1}-S_{i-2} \lt S_i-S_{i-1}}を満たす最長の上昇部分列の長さを今選んでいる要素のindex,直前に選んだ要素のindexの情報を持った上で求める.下はA= \left\{1,7,5,3,1,6,3,9,1 \right\} のときの例.各 iに対する最大値が A_iを最後に使ったときの最長の上昇部分列長である.自分の提出は左からの上昇列長を求めたら,Aを反転して同一の処理をしている.

f:id:ctylim:20160224181654p:plain:w500

yukicoder No.209


想定解が Q \leq 100, N \leq 100 O(QN^3) なのだけれど,意外と間に合うのね.