MyBlogs[ARC180E]LISandInversion首先考虑要求代价为\(0\)的一个暴力DP：\(f_{i,j}\)表示填了前\(i\)个数，此时相对值域末尾为\(j\)的数结尾的LIS的最大值。填第\(i+1\)个数的时候，把它插在某两个数之间，所以转移是：\[f_{i,j}=\begin{cases}f_{i-1,j-1}\qquad\qqua

题目大意一个排列\(p\)分数为\(p\)的最长上升子序列的长度，代价为满足\(\sum_{j=1}^{i-1}[p_j>p_i]<a_{i}\)的\(i\)的数量给定\(\{a_n\}\)，对于\(\forallk\in[1,n]\)，求分数大于等于\(k\)的排列的代价的最小值\[n\leq250000,1\leqa_i<i\]题解玄妙优化\(dp\)题我们可以考虑求