题目概述
给你一个排列 \(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\) 前面，否则就不可能使其升序。
那么我们就可以推出来其中一个的状态转移方程：
为什么在 \(k<j\) 时是 \([p_k<i]\) 呢？
比如说：\([1,3,4,2,5]\) 中，假设 \(5\) 是不动点，那我处理到 \(2\) 的时候算他要到达的目的地就是就是位置 \(2\)，因为 \(3,4\) 比他大先处理，所以就已经紧贴着 \(5\) 了。
我不移动这个 \(i\)
显然 \(j\) 一定大于 \(pos_i\)，否则不可能成立。
那我们试图通过，两个不动点 \(pos_i,j\) 能否求出 \(b\)，使得气的费用提前。
我们发现当我们不移动 \(i\) 时，那么位于 \([pos_i+1,j-1]\) 的比 \(i\) 小的点一定要动！而且要动到 \(pos_i\) 的前面。
设 \(k\in[pos_i+1,j-1]\) 那么如果 \(p_k<i\)，那么就要动，对其的贡献为 \(i-p_k\)。
至于为什么呢？咳咳。
代码
#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <cstring>
#include <algorithm>
#include <vector>
#define int long long
#define N 2005
using namespace std;
int n,p[N],f[N][N],pos[N];
signed main(){cin >> n;for (int i = 1;i <= n;i ++) scanf("%lld",&p[i]),p[i] = n + 1 - p[i],pos[p[i]] = i;memset(f,0x3f,sizeof f);f[n + 1][n + 1] = 0,p[n + 1] = n + 1;pos[n + 1] = n + 1;for (int i = n;i;i --) {int c1 = 1,c2 = 1;for (int j = 1;j < pos[i];j ++) c1 += (p[j] < i);for (int j = 1;j <= n + 1;j ++) {c2 += (p[j] < i);f[i][j] = min(f[i][j],f[i + 1][j] + c1 + c2);}int sum = 0;for (int j = pos[i] + 1;j <= n + 1;j ++) {f[i][pos[i]] = min(f[i][pos[i]],f[i + 1][j] + sum);if (i > p[j]) sum += i - p[j];}}int ans = 1e18 + 7;for (int i = 1;i <= n + 1;i ++) ans = min(ans,f[1][i]);cout << ans;return 0;
}