记忆排列题目分析

题目概述

给你一个排列 \(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<pos_i}[p_k<i]+1+\sum_{k<j}[p_k<i]+1 \]

为什么在 \(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\)。

至于为什么呢？咳咳。

我们举个例子：\([3,6,2,4,10]\)，然后我们就 \(7\) 的位置讨论（如果比 \(6\) 小的话肯定在前面），固定 \(6,10\) 两个数字，讨论一下比 \(5\) 小的 \(2,4\)。

假设 \(5\) 在 \(6\) 的前面。

那么类似于 \([3,5,6,2,4,10]\)，那么我们的 \(4\) 是不是没有算 \(5,6\) 两个比他大的数到他的初始位置 \(x\) 中，而 \(2\) 是不是没有算 \(3,5,6\) 三个比他大的数（这是原本在前面的）还有在他后面的 \(4\)（由于先进行操作，所以 \(4\) 又到他前面了）。

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

假设 \(5\) 在 \(6\) 后面。

跟计算 \(2\) 时一样，\(5\) 就会先跑到前面去。

于是我们不难得出这里少了的贡献是 \(i-p_k\)。

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

于是我们就得到了：

\[f_{i,pos_i}=f_{i+1,j}+\sum_{k\in[pos_i+1,j-1]}\max(i-p_k,0) \]

两者结合便是正道题目的状态转移方程，其时间复杂度为 \(\mathcal{O}(n^2)\)。

代码

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

来源链接：https://www.cnblogs.com/high-sky/p/19012663