发现我们可以固定里面一段上升子序列不动，我们称这些子序列的点为“选定点”
我们不妨能发现答案为非选定点的个数，而放“0球”的个数则为非选定点连续段个数
于是我们考虑dp，设\(dp_{i,j}\)表示前\(i\)个数，钦定\(i\)为选定点，前面出了\(j\)个非选定点的连续段
容易想到递推柿子：
\[dp_{i,j}=\min_{k=1,a_k<a_i}^n{(dp_{k,j-1}+i-k)}
\]
最终答案为\(\min_{i=1}^{n}{(dp_{i,k}+n-i)}\)
CF1839D
发布时间 2023-08-23 19:56:10作者: FOX_konata