AT4519[AGC032D]Rotation Sort【dp】

正题

题目链接:https://www.luogu.com.cn/problem/AT4519

---

题目大意

给出一个长度为\(n\)的排列，每次可以选择一个区间，然后花费\(A\)的代价向左旋转（最左边的丢到最右边）或者花费\(B\)的代价向右旋转。
排升序序的最小花费。

\(1\leq n\leq 5000\)

---

解题思路

相当于向右丢和向左丢。因为位置不固定非常麻烦，我们可以考虑统计那些顺序固定的。

设\(f_i\)表示做到第\(i\)个且第\(i\)个不动的最小花费，然后考虑\(f_j\)转移到\(f_i\)时的代价，那么显然我们要把中间数都变成在\(a_j\)到\(a_i\)之间，所以把其中所有大于\(a_i\)的往右丢，小于\(a_j\)的往左丢。
这样可以做到\(O(n^3)\)或者用数据结构做到\(O(n^2\log n)\)

但是我们考虑到小于\(a_j\)的同时也是小于\(a_i\)的，如果我们把所有小于\(a_i\)的都往左丢，这样不会出现更小的答案，所以不会被统计到里面。

这样就只和\(a_i\)有关了，倒序枚举\(j\)然后\(O(n^2)\)转移即可。

用线段树可以做到\(O(n\log n)\)

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=5100;
ll n,A,B,a[N],f[N];
signed main()
{
	scanf("%lld%lld%lld",&n,&A,&B);
	for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);
	memset(f,0x3f,sizeof(f));
	a[0]=-1;++n;a[n]=n;f[0]=0;
	for(ll i=1;i<=n;i++){
		ll up=0,dn=0;
		for(ll j=i-1;j>=0;j--){
			if(a[j]<a[i])f[i]=min(f[i],f[j]+up*A+dn*B);
			if(a[j]>a[i])up++;else dn++;
		}
	}
	printf("%lld\n",f[n]);
}