题目概述给你一个排列 共有 个元素你可以选择两个数 然后将 移动到位置 这个过程需要花费 的代价问你通过这些操作过后所能使 变为降序的最小代价。思路变成降序似乎不是我们所擅长的我们先转化为变成升序这个是容易的只需要令 即可。我们先考虑暴力的做法总结出来一些性质每个数显然只能移动一次如果移动了两次还不如一步到位。按照从大到小的顺序移动这些数比按照其他顺序移动更好。因此我们可以得到 的暴力。然后我们继续思考可以让一些点不动然后进行 。假设我们从后往前处理到了权值为 的点令其原始位置为 现在我们假设移动前的位置为 移动后的位置为 。我们令 其中 表示在 的前面在原始序列当中且权值比 要小的点的个数加上 需要求得是排名根据题目代价这些点没有处理过一定是在 移动前的位置的前面的。而 表示在 的前面在原始序列当中且权值比 要大的点且是不移动的点的个数这些点是处理过的然而我们并不知道所以先不管之后处理。同理 也可以通过 的类似计算得到。通过这个分析我们可以设 表示处理到权值为 的点最小不动点的位置为 的最小代价。然后分以下情况讨论当前我要移动这个那么显然的无论我们是在 的前面还是后面一定至少挪到 前面否则就不可能使其升序。那么我们就可以推出来其中一个的状态转移方程为什么在 时是 呢比如说 中假设 是不动点那我处理到 的时候算他要到达的目的地就是就是位置 因为 比他大先处理所以就已经紧贴着 了。我不移动这个显然 一定大于 否则不可能成立。那我们试图通过两个不动点 能否求出 使得其的费用提前。我们发现当我们不移动 时那么位于 的比 小的点一定要动而且要动到 的前面。设 那么如果 那么就要动对其的贡献为 。至于为什么呢咳咳。我们举个例子然后我们就 的位置讨论如果比 小的话肯定在前面固定 两个数字讨论一下比 小的 。假设 在 的前面。那么类似于 那么我们的 是不是没有算 两个比他大的数到他的初始位置 中而 是不是没有算 三个比他大的数这是原本在前面的还有在他后面的 由于先进行操作所以 又到他前面了。如果说 在 后面的话那么已经算过贡献了故不用再次计算。假设 在 后面。跟计算 时一样 就会先跑到前面去。于是我们不难得出这里少了的贡献是 。但是为什么要加到 之中呢其实无所谓到最后都会执行到 然后前者只跟他的下一个有关因此不需要细究到某一次操作当中只需要考虑总体情况的大小即可。于是我们就得到了两者结合便是正道题目的状态转移方程其时间复杂度为 。代码#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]; }