近一个月来第一次赛时通过一道题。真是可喜可贺。
一开始以为与网络流相关；后来考虑 DP；结果是个贪心或者乱搞。
给定长为 $\newcommand\bigO{\operatorname{O}}n\ \ (n\leq 10^5)$ 的序列 $\langle a_i\rangle,a_i\in\{1,2,3\}$。匹配尽可能多的子序列，每个子序列均为 $\langle 1,2,3\rangle$ 或 $\langle 3,2,1\rangle$，且一个位置最多被一个子序列占用。求最大匹配数。 （更多…）
设 $f(i,j,0/1/2)$ 表示第 $i$ 天持有 $j$ 支股票，并且当天进行了 持有 / 买 / 卖 操作，所能获得的最大的收益。很容易想到以下转移：
$$\begin{aligned}&f(i,j,0) = \max \{f(k,j,t) \mid k < i,t\in\{0,1,2\}\}; \\
&f(i,j,1)= \max \{f(k,p,t) \mid k < i-w, p \leq j,t\in\{0,1,2\}\}; \\
&f(i,j,2)= \max \{f(k,p,t) \mid k < i-w, p \geq j,t\in\{0,1,2\}\} \end{aligned}$$