题解：P17148 [ICPC 2017 Xi'an R] Naomi with Array

· · 题解

题意简述

给定一个元素互异的数组。 一次操作可以取出位置 i 的元素，再把它插入位置 j， 代价为 i+j。

求把数组变为严格降序的最小总代价。 在总代价最小的方案中，还要最小化操作次数。 输入包含若干组数据，读到文件末尾为止。

解题思路

按数值从大到小把元素离散化为 1,2,\dots,n。 目标数组就变成编号递增的排列。 记编号 i 的原位置为 p_i， 位置 j 上的编号为 a_j。

一次移动的代价可以看成两个端点的贡献。 删除位置与插入位置各先贡献 1， 每个位于对应端点之前的现存元素再贡献 1。

先说明一个端点计费引理。 把所有移动按元素编号从大到小重新结算时， 可以把尚未处理的较小元素保留在原位置， 并把它们引起的端点平移延后计算。 每次有一个端点跨过较小元素，恰好产生一个单位贡献， 所以这种计费顺序不会改变总代价。

若同一元素被移动多次， 可以把第一次删除到最后一次插入合并为一次移动。 中间每次重新插入和删除都会多出两个基础端点， 却不会减少必须发生的端点平移。 因此合并后总代价不会增加，操作次数只会减少。 只需考虑每个元素至多移动一次的方案。

不移动的元素会保持原相对顺序。 所以它们的编号递增时，原位置也必须递增。 反过来，任取一个满足该条件的保留集合， 其余元素都能按编号从大到小插入到目标位置。

于是从编号 n 到 1 决定每个元素移动还是保留。 已经处理完编号 i+1,\dots,n 时， 令 d 为其中编号最小的保留元素的原位置。 若还没有保留元素，就令 d=n+1。 后续只需知道这个最靠左的锚点。

处理编号 i 时，定义前缀量：

\begin{aligned} c_j & =\sum_{t=1}^j[a_t<i] \\ s_j & =\sum_{\substack{1\leq t\leq j\\a_t<i}}(i-a_t) \end{aligned}

其中 [P] 在命题 P 成立时为 1，否则为 0。

若移动编号 i，删除端点的贡献为：

L_i=1+c_{p_i-1}

插入位置位于当前锚点 d 之前，对应贡献为：

R_{i,d}=1+c_{d-1}

较大编号造成的平移已经在此前结算， 尚未处理且仍位于两个端点之前的元素正好由这两个前缀计数得到。

若保留编号 i，必须满足 p_i<d。 原位置严格位于 p_i 与 d 之间的较小编号， 需要跨过从自身编号到 i 的连续编号段。 编号 a_t 对尚未结算的端点平移贡献为 i-a_t。 因此把锚点从 d 改为 p_i 时，需要补上：

C_{i,d}=s_{d-1}-s_{p_i}

令 f_{i,d} 表示已经决定编号 i,i+1,\dots,n， 且当前锚点为 d 时的最优二元组。 二元组依次保存总代价和操作次数，按字典序比较。

移动编号 i 不改变锚点，转移为：

f_{i,d}=f_{i+1,d}+(L_i+R_{i,d},1)

保留编号 i 会把锚点改为 p_i，转移为：

f_{i,p_i}=\min_{d>p_i}\{f_{i+1,d}+(C_{i,d},0)\}

初始时还没有处理任何元素，只有哨兵锚点：

f_{n+1,n+1}=(0,0)

按照端点计费引理，移动转移恰好结算编号 i 的两个操作端点； 保留转移则结算两个相邻锚点之间被延后的平移贡献。 每个方案在编号 i 处只能选择移动或保留之一， 两类转移互不遗漏。 归纳到 i=1 后，每个端点贡献都被计算一次， 所以所有状态中的最小二元组就是答案。

每层先线性计算 c_j,s_j，再枚举旧锚点 d。 动态规划只保留相邻两层。 时间复杂度为 O(n^2)，空间复杂度为 O(n)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using pii=pair<int,int>;
const int N=1005;
const int inf=0x3f3f3f3f;
int a[N],pos[N],cnt[N],sum[N];
pii b[N];
pii f[N];
pii g[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while(cin>>n)
    {
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            b[i]={x,i};
        }
        sort(b+1,b+n+1,greater<pii>());
        for(int i=1;i<=n;i++)
        {
            a[b[i].second]=i;
            pos[i]=b[i].second;
        }
        a[n+1]=n+1;
        for(int i=1;i<=n+1;i++)f[i]={inf,inf};
        f[n+1]={0,0};
        for(int i=n;i>=1;i--)
        {
            cnt[0]=0;
            sum[0]=0;
            for(int j=1;j<=n+1;j++)
            {
                cnt[j]=cnt[j-1];
                sum[j]=sum[j-1];
                if(a[j]<i)
                {
                    cnt[j]++;
                    sum[j]+=i-a[j];
                }
                g[j]={inf,inf};
            }
            int p=pos[i];
            int l=cnt[p-1]+1;
            for(int j=1;j<=n+1;j++)
            {
                if(f[j].first==inf)continue;
                g[j]={f[j].first+l+cnt[j-1]+1,f[j].second+1};
                if(j>p)
                {
                    pii v={f[j].first+sum[j-1]-sum[p],f[j].second};
                    g[p]=min(g[p],v);
                }
            }
            for(int j=1;j<=n+1;j++)f[j]=g[j];
        }
        pii ans={inf,inf};
        for(int i=1;i<=n+1;i++)ans=min(ans,f[i]);
        cout<<ans.first<<' '<<ans.second<<'\n';
    }
    return 0;
}