[AGC032D] Rotation Sort 题解

题目链接

点击打开链接

题目解法

题目中的操作可以理解为一个点移动位置
首先给出一个结论：每个点只会动至多一次
考虑 \(dp\)
一个比较妙的状态设定是 \(f_i\) 表示 \(i\) 不动的方案数
不妨枚举 \(j\) 表示上一个不动点，限制是 \(j<i\) 且 \(p_j<p_i\)
中间满足 \(j<k<i\) 且 \(p_k>p_i\) 的都要移到 \(i\) 后面，代价为 \(A\)
中间满足 \(j<k<i\) 且 \(p_k<p_j\) 的都要移到 \(j\) 前面，代价为 \(B\)
中间其他的点需要动，且需要排成一个顺序，一个显然的结论是，每个点都只往左边或右边动可以得到任意一个顺序，所以代价为 \(\min(A,B)\)

时间复杂度 \(O(n^2)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=5100;
int n,A,B,a[N],s[N][N];
LL f[N];
int main(){
    read(n),read(A),read(B);
    F(i,1,n) read(a[i]);
    F(i,1,n) F(j,1,n)
        if(a[j]<a[i]) s[i][j]=s[i][j-1]+1;
        else s[i][j]=s[i][j-1];
    memset(f,0x3f,sizeof(f));
    f[0]=0,a[n+1]=1e9;
    F(i,1,n+1){
        int rs1=0;
        DF(j,i-1,0){
            if(a[j]<a[i]){
                int rs2=s[j][i-1]-s[j][j];
                chkmin(f[i],f[j]+1ll*rs2*B+1ll*rs1*A+1ll*(i-j-1-rs1-rs2)*min(A,B));
            }
            rs1+=a[j]>a[i];
        }
    }
    printf("%lld\n",f[n+1]);
    return 0;
}