主要思路

这道题还是很有意思的，建图方式非常的巧妙。首先我们先把第一问的 DP 用 \(O(n \log n)\) 的时间求解一下，顺便搞到一个数组\(f[i]\)，含义是以\(i\)为结尾的最长子序列长度。建图的时候要注意的是，每一个位置对应的点要拆成两个：这是为了保持答案的唯一性。所以对于\(f[i]=1\)的点\(i\)，连边\((s,i)\)；对于\(f[i]=k\)的点\(i\)，连边\((i+n,t)\)。之后，如果对于\((u,v), f[v] = f[u] + 1, arr[u] \leq arr[v]\)进行连边，跑个最大流就可以出答案了。

第三问其实跟第二问的差不多，只需要把点\(1\)和点\(n\)的外向边（到源点或者是汇点的边）的最大流限制改成无穷大即可。