题解：P7406 [JOI 2021 Final] 集体照 / Group Photo

· · 题解

又没看懂题解，于是写了一份特别奇怪的代码，然后过了。

于是我准备写一篇非常详细的题解。

设排序后在第 i 个位置的人身高为 a_i，那么 a_{i+1}-a_i>=-1，因此后面的比前面的大，或者后面的比前面的小 1。如果我们把连续的 a_{i+1}-a_i = -1 放到一起，就是一段连续的公差为 1 的等差数列。为避免歧义，我们在这里只称这样的子区间为连续段。下面先放一些性质，每一个都不难想，但放到一起就是答案：

性质 1：如果最终序列中某段等差数列的结尾为 l，则 a_1 到 a_l 的值域为 [1,l]。也就是说下一个连续段末尾的数一定比当前连续段的起始位置的数大 1。

性质 2：对于某一值域内的交换不会影响其他不在至于内的数的顺序，也就是说交换可能改变实际位置，但步改变值域外的数的相对位置。

性质 3：根据性质 2，我们不难发现总交换次数等于不同段之间的逆序对数加上每段内的顺序对数，因此新连续段只需要统计比它更大的数的逆序对就可以。

因此我们现在需要预处理两个东西，一个是值域 [i,j] 的顺序对数，一个是值域 [i,j] 与值域 [j+1,n] 的逆序对数。这部分应该是好做的，用好前后缀和思想就可以。

然后就到了 dp 部分，设 f_{i,j} 表示放了前 i 位末尾为 j，这样就能得到最后一段，因为最后一段一定是 [j,i]。然后我们就能用 \min\limits_{k=1}^{i-j} f_{i-j,k} 加上之前统计的 [j,i] 之间的顺序对数，再加上 [j,i] 与 [i+1,n] 之间的逆序对数就能得到 f_{i,j}。时间和空间复杂度否是 O(n^2)，注意空间限制。


#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define lb lower_bound
#define fr front()
#define pii pair<int,int>
#define INF 1e18
using namespace std;

int n,a[5005],f[5005][5005],g[5005][5005],h[5005];
int p[5005][5005],c[5005][5005];

void solve1(){
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(a[i]<a[j]){
                g[a[i]][a[j]]++;
                p[a[i]][a[j]]++;c[a[j]][a[i]]++;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=i+2;j<=n;j++)p[i][j]+=p[i][j-1];
        for(int j=i-2;j>=1;j--)c[i][j]+=c[i][j+1];
    }
    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int l=i,r=i+len-1;
            g[l][r]+=g[l+1][r-1]+p[l][r-1]+c[r][l+1];
            //中间部分，包含左端点的，包含右端点的
        }
    }
}//统计顺序对部分

void solve2(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)p[i][j]=0,c[i][j]=0;
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(a[i]>a[j])p[a[j]][a[i]]++;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=n;j>=1;j--)p[i][j]+=p[i][j+1];
    }
    //这样统计出来了i与[j+1,n]的逆序对数
    for(int i=n-1;i>=1;i--){
        for(int j=n-1;j>=i;j--){
            c[i][j]=c[i+1][j]+p[i][j+1];
        }
    }
}//统计逆序对部分

signed main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    solve1();solve2();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++)f[i][j]=INF;
        h[i]=INF;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            f[i][j]=h[j-1]+g[j][i]+c[j][i];
        }
        for(int j=1;j<=i;j++)h[i]=min(h[i],f[i][j]);
    }
    cout<<h[n];
}