P6323

prob

不会做黄题。水平退化成啥了。

Solution

这类与全排列相关的 dp 题。常见的套路是从小到大填数。本题中考虑 \(f_{i,j}\) 表示填了 \(1 \sim i\)，逆序对数为 \(j\)。

考虑第 \(i\) 个数插在哪里以及对应的贡献。此时序列中的数只有小于 \(i\) 和大于 \(i\) 两种情况。当前已经插了 \(i-1\) 个数，你会发现只有 \(i\) 个位置是需要考虑的，分别对应了造了 \(0 \sim i-1\) 个逆序对。那么这样转移就做到 \(O(n^2c)\) 了。