记忆排列题目分析

题目概述

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

思路

变成降序似乎不是我们所擅长的，我们先转化为变成升序，这个是容易的只需要令 即可。

我们先考虑暴力的做法，总结出来一些性质：

• 每个数显然只能移动一次，如果移动了两次还不如一步到位。

• 按照从大到小的顺序移动这些数比按照其他顺序移动更好。

因此我们可以得到 的暴力。

然后我们继续思考，可以让一些点不动，然后进行 。

假设我们从后往前处理到了权值为 的点，令其原始位置为 ，现在我们假设移动前的位置为 ，移动后的位置为 。

我们令 ，其中 表示在 的前面（在原始序列当中），且权值比 要小的点的个数加上 （需要求得是排名，根据题目代价），这些点没有处理过，一定是在 移动前的位置的前面的。而 表示在 的前面（在原始序列当中），且权值比 要大的点且是不移动的点的个数，这些点是处理过的，然而我们并不知道，所以先不管，之后处理。

同理， 也可以通过 的类似计算得到。

通过这个分析，我们可以设 表示处理到权值为 的点，最小不动点的位置为 的最小代价。

然后分以下情况讨论：

当前我要移动这个

那么显然的，无论我们是在 的前面还是后面，一定至少挪到 前面，否则就不可能使其升序。

那么我们就可以推出来其中一个的状态转移方程：

为什么在 时是 呢？

比如说： 中，假设 是不动点，那我处理到 的时候算他要到达的目的地就是就是位置 ，因为 比他大先处理，所以就已经紧贴着 了。

我不移动这个

显然 一定大于 ，否则不可能成立。

那我们试图通过，两个不动点 能否求出 ，使得其的费用提前。

我们发现当我们不移动 时，那么位于 的比 小的点一定要动！而且要动到 的前面。

设 那么如果 ，那么就要动，对其的贡献为 。

至于为什么呢？咳咳。

我们举个例子：，然后我们就 的位置讨论（如果比 小的话肯定在前面），固定 两个数字，讨论一下比 小的 。

假设 在 的前面。

那么类似于 ，那么我们的 是不是没有算 两个比他大的数到他的初始位置 中，而 是不是没有算 三个比他大的数（这是原本在前面的）还有在他后面的 （由于先进行操作，所以 又到他前面了）。

如果说 在 后面的话，那么已经算过贡献了，故不用再次计算。

假设 在 后面。

跟计算 时一样， 就会先跑到前面去。

于是我们不难得出这里少了的贡献是 。

但是为什么要加到 之中呢？其实无所谓，到最后都会执行到 ，然后前者只跟他的下一个有关，因此，不需要细究到某一次操作当中，只需要考虑总体情况的大小即可。

于是我们就得到了：

两者结合便是正道题目的状态转移方程，其时间复杂度为 。

代码

#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]; }