记忆排列题目分析

大丫头 發表於 2025-7-30 12:27:00

<h2 id="题目概述">题目概述</h2>
给你一个排列 \(p\)，共有 \(n\) 个元素，你可以选择两个数 \(i,j\)，然后将 \(p_i\) 移动到位置 \(j\)，这个过程需要花费 \(i+j\) 的代价，问你通过这些操作过后所能使 \(p\) 变为降序的最小代价。
<h2 id="思路">思路</h2>
变成降序似乎不是我们所擅长的，我们先转化为变成升序，这个是容易的只需要令 \(p_i=n-p_i+1\) 即可。
我们先考虑暴力的做法，总结出来一些性质：
<ul>
<li>
每个数显然只能移动一次，如果移动了两次还不如一步到位。
</li>
<li>
按照从大到小的顺序移动这些数比按照其他顺序移动更好。
</li>
</ul>
因此我们可以得到 \(\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\) 的最小代价。
然后分以下情况讨论：
<h3 id="当前我要移动这个-">当前我要移动这个 \(i\)</h3>
那么显然的，无论我们是在 \(j\) 的前面还是后面，一定至少挪到 \(j\) 前面，否则就不可能使其升序。
那么我们就可以推出来其中一个的状态转移方程：
<div class="math display">\+1+\sum_{k<j}+1
\]</div>为什么在 \(k<j\) 时是 \(\) 呢？
比如说：\(\) 中，假设 \(5\) 是不动点，那我处理到 \(2\) 的时候算他要到达的目的地就是就是位置 \(2\)，因为 \(3,4\) 比他大先处理，所以就已经紧贴着 \(5\) 了。
<h3 id="我不移动这个-">我不移动这个 \(i\)</h3>
显然 \(j\) 一定大于 \(pos_i\)，否则不可能成立。
那我们试图通过，两个不动点 \(pos_i,j\) 能否求出 \(b\)，使得其的费用提前。
我们发现当我们不移动 \(i\) 时，那么位于 \(\) 的比 \(i\) 小的点一定要动！而且要动到 \(pos_i\) 的前面。
设 \(k\in\) 那么如果 \(p_k<i\)，那么就要动，对其的贡献为 \(i-p_k\)。
至于为什么呢？咳咳。
我们举个例子：\(\)，然后我们就 \(7\) 的位置讨论（如果比 \(6\) 小的话肯定在前面），固定 \(6,10\) 两个数字，讨论一下比 \(5\) 小的 \(2,4\)。
<h4 id="假设--在--的前面">假设 \(5\) 在 \(6\) 的前面。</h4>
那么类似于 \(\)，那么我们的 \(4\) 是不是没有算 \(5,6\) 两个比他大的数到他的初始位置 \(x\) 中，而 \(2\) 是不是没有算 \(3,5,6\) 三个比他大的数（这是原本在前面的）还有在他后面的 \(4\)（由于先进行操作，所以 \(4\) 又到他前面了）。
如果说 \(4\) 在 \(10\) 后面的话，那么已经算过贡献了，故不用再次计算。
<h4 id="假设--在--后面">假设 \(5\) 在 \(6\) 后面。</h4>
跟计算 \(2\) 时一样，\(5\) 就会先跑到前面去。
于是我们不难得出这里少了的贡献是 \(i-p_k\)。
但是为什么要加到 \(f_{i,pos_i}\) 之中呢？其实无所谓，到最后都会执行到 \(f_{1,x}\)，然后前者只跟他的下一个有关，因此，不需要细究到某一次操作当中，只需要考虑总体情况的大小即可。
于是我们就得到了：
<div class="math display">\}\max(i-p_k,0)
\]</div>两者结合便是正道题目的状态转移方程，其时间复杂度为 \(\mathcal{O}(n^2)\)。
<h2 id="代码">代码</h2>
<pre><code class="language-cpp">#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,f,pos;
signed main(){
cin >> n;
for (int i = 1;i <= n;i ++) scanf("%lld",&p),p = n + 1 - p,pos] = i;
memset(f,0x3f,sizeof f);
f = 0,p = n + 1;
pos = n + 1;
for (int i = n;i;i --) {
int c1 = 1,c2 = 1;
for (int j = 1;j < pos;j ++) c1 += (p < i);
for (int j = 1;j <= n + 1;j ++) {
c2 += (p < i);
f = min(f,f + c1 + c2);
}
int sum = 0;
for (int j = pos + 1;j <= n + 1;j ++) {
f] = min(f],f + sum);
if (i > p) sum += i - p;
}
}
int ans = 1e18 + 7;
for (int i = 1;i <= n + 1;i ++) ans = min(ans,f);
cout << ans;
return 0;
}
</code></pre> 
来源：https://www.cnblogs.com/high-sky/p/19012663

頁: [1]

琼殿技术论坛's Archiver

记忆排列题目分析