记忆排列题目分析

题目概述

给你一个排列 \(p\)，共有 \(n\) 个元素，你可以选择两个数 \(i,j\)，然后将 \(p_i\) 移动到位置 \(j\)，这个过程需要花费 \(i+j\) 的代价，问你通过这些操作过后所能使 \(p\) 变为降序的最小代价。
思路

变成降序似乎不是我们所擅长的，我们先转化为变成升序，这个是容易的只需要令 \(p_i=n-p_i+1\) 即可。
我们先考虑暴力的做法，总结出来一些性质：

• 每个数显然只能移动一次，如果移动了两次还不如一步到位。
  
• 按照从大到小的顺序移动这些数比按照其他顺序移动更好。
  

因此我们可以得到 \(\mathcal{O}(n2^n)\) 的暴力。
然后我们继续思考，可以让一些点不动，然后进行 \(dp\)。
假设我们从后往前处理到了权值为 \(i\) 的点，令其原始位置为 \(pos_i\)，现在我们假设移动前的位置为 \(x\)，移动后的位置为 \(y\)。
我们令 \(x=a + b\)，其中 \(a\) 表示在 \(i\) 的前面（在原始序列当中），且权值比 \(i\) 要小的点的个数加上 \(1\)（需要求得是排名，根据题目代价），这些点没有处理过，一定是在 \(i\) 移动前的位置的前面的。而 \(b\) 表示在 \(i\) 的前面（在原始序列当中），且权值比 \(i\) 要大的点且是不移动的点的个数，这些点是处理过的，然而我们并不知道，所以先不管，之后处理。
同理，\(y\) 也可以通过 \(a\) 的类似计算得到。
通过这个分析，我们可以设 \(f_{i,j}\) 表示处理到权值为 \(i\) 的点，最小不动点的位置为 \(j\) 的最小代价。
然后分以下情况讨论：
当前我要移动这个 \(i\)

那么显然的，无论我们是在 \(j\) 的前面还是后面，一定至少挪到 \(j\) 前面，否则就不可能使其升序。
那么我们就可以推出来其中一个的状态转移方程：

\[f_{i,j}=f_{i+1,j}+a+y=f_{i+1,j}+\sum_{k