AtCoder Grand Contest 032D - Rotation Sort

题目

Description

有一个长度为$n$的排列,每次可以选择一个区间,把区间所有数向左或向右移动一格(像环一样,多出来那个数回到最左或最右的位置),向左和向右的代价分别为$A$和$B$,求排好序的最小代价

Solution

考虑旋转操作的本质,如果第$i$个数要放到位置$j$与$j+1$中间,且$i<j$,那么$[i,j]$向左转一下即可,$i>j$同理

1.二维dp

$f[i][j]$表示把前$i$个数排好序,$j$是最后一个(可以理解为当前)没有移动的数的最小代价

$j<a[i]​$,并且$j​$和$a[i]​$的相对位置不对,那么$f[i][j]=f[i-1][j]+A​$(把$a[i]​$放到$j​$右侧的某一个正确的位置)

$j<a[i]$,并且$j$和$a[i]$的相对位置对了,那么$f[i][a[i]]=f[i-1][j]$($a[i]$不用动)

$j>a[i]$,那么$f[i][j]=f[i-1][j]+B$(把$a[i]$放到$j$左侧的某一个正确的位置)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5002;
int n,A,B,a[N],i,j;
ll f[N][N],ans=1e18,tmp;
inline void Min(ll &x,ll y){if(y<x)x=y;}
int main(){
scanf("%d%d%d",&n,&A,&B);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
memset(f,63,sizeof(f));
f[0][0]=0;
for (i=1;i<=n;i++)
for (j=0;j<=n;j++){
tmp=f[i-1][j];
if (j<a[i]) Min(f[i][a[i]],tmp),Min(f[i][j],tmp+A);
else Min(f[i][j],tmp+B);
}
for (i=1;i<=n;i++) Min(ans,f[n][i]);
printf("%lld",ans);
}

2.一维dp

$f[i]​$表示以$i​$为基准,并且前$i​$个点排好序的最小代价,

$f[i]=min \lbrace f[j]+(j+1…i-1中大于a[i]的数左转,小于a[i]的数右转的代价总和) \rbrace$

因为最后不知道以哪个数为基准最好,为了便于统计,令$a[n+1]=n+1$,最后输出$f[n+1]$即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
const int N=5002;
int n,A,B,a[N],i,j;
long long f[N],tot;
int main(){
scanf("%d%d%d",&n,&A,&B);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
a[n+1]=n+1,n++;
memset(f,63,sizeof(f));
f[0]=0;
for (i=1;i<=n;i++){
tot=0;
for (j=i-1;~j;j--)
if (a[j]<a[i]) f[i]=min(f[i],f[j]+tot),tot+=B;
else tot+=A;
}
printf("%lld",f[n]);
}

可能有人会担心$A$很小,$B$很大,然后出现2 3 4 1这种情况,应该向左三次而不是向右一次,事实上,只要改变一下基准位置,一切就迎刃而解,而这些都已经在程序里有了,所以不用担心