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