CF1144G Two Merged Sequences

题意

现在给你一个长度为\(n\)的序列

你要把它拆成一个严格递增序列和一个严格递减序列

如果不可行输出\(NO\)

如果可行输出\(YES\)并输出每个数属于递增序列还是递减序列

题解

感觉脑子瓦特了，感觉这个 \(dp\) 的状态设计是比较自然的。
首先我们考虑一个数字的归属，要么是属于上升子序列要么是属于下降子序列。
而一个数如果接在了末尾显然是最大/最小的，而我们判断能不能接上只需要知道最后一个就行了。
而转移的时候知道前一个的归属也就知道了其中一个序列的最值，显然我们还要记录的就是另一个序列的最值，所以设 \(f_{i,0/1}\)。
\(f_{i,0}\) 表示当 \(a_i\) 属于上升序列时下降序列的最小值。
\(f_{i,1}\) 表示当 \(a_i\) 属于下降序列时上升序列的最大值。
然后这个转移就很显然了，输出方案时记录一下转移的来源就好了。 code