AGC032D Rotation Sort

Description

给定\(N\)的排列（\(N\leq5000\)），将任一区间最左侧的数插到该区间最右边的代价为\(A\)，将任一区间最右侧的数插到该区间最左边的代价为\(B\)，问将该排列排为升序的最小代价。

Solution

显然有一个\(O(n^3)\)的区间\(dp\)方法，但与正解无关。

考虑操作的实际效果，其实就是将一个数向前或后移，并不需要管它移到哪里，因为所有数都向任一方向移动就一定能到达升序。

所以我们只要考虑没有移动的位置，设\(dp_{i,j}\)为考虑前\(i\)个数，前\(i\)个钟最后一个没有移动的数为\(j\)的最小代价，分\(a_i>j\)及\(a_i<j\)转移即可。

细节见代码：

#include<cstdio>

#include<cstring>

#define int long long

#define rep(i, a, b) for (register int i=(a); i<=(b); ++i)

#define per(i, a, b) for (register int i=(a); i>=(b); --i)

using namespace std;

typedef long long ll;

inline void chkmax(int &x, int y){x<y?(x=y):0;}

inline void chkmin(int &x, int y){x>y?(x=y):0;}

const int N=5005;

int dp[N][N], a[N];

inline int read()

{

    int x=0,f=1;char ch=getchar();

    for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;

    for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';

    return x*f;

}

signed main()

{

	int n=read(), A=read(), B=read(), ans=1ll<<60;

	rep(i, 1, n) a[i]=read();

	memset(dp, 0x3f, sizeof(dp)); dp[0][0]=0;

	rep(i, 1, n) rep(j, 0, n)

		if (a[i]>j)

			chkmin(dp[i][j], dp[i-1][j]+A),

			chkmin(dp[i][a[i]], dp[i-1][j]);

		else

			chkmin(dp[i][j], dp[i-1][j]+B);

	rep(i, 0, n) chkmin(ans, dp[n][i]);

	printf("%lld\n", ans);

	return 0;

}

巴特西

AGC032D Rotation Sort

Description

Solution

最新文章

热门文章