主要思路
我们首先可以搞到一个统计答案的式子:
这道题还是很有意思的,建图方式非常的巧妙。首先我们先把第一问的 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\)的外向边(到源点或者是汇点的边)的最大流限制改成无穷大即可。