Description
给定 \(N\) 的排列 (\(N\leq5000\)), 将任一区间最左侧的数插到该区间最右边的代价为 \(A\), 将任一区间最右侧的数插到该区间最左边的代价为 \(B\), 问将该排列排为升序的最小代价.
Solution
显然有一个 \(O(n^3)\) 的区间 \(dp\) 方法, 但与正解无关.
考虑操作的实际效果, 其实就是将一个数向前或后移, 并不需要管它移到哪里, 因为所有数都向任一方向移动就一定能到达升序.
所以我们只要考虑没有移动的位置, 设 \(dp_{i,j}\) 为考虑前 \(i\) 个数, 前 \(i\) 个钟最后一个没有移动的数为 \(j\) 的最小代价, 分 \(a_i>j\) 及 \(a_i<j\) 转移即可.
细节见代码:
- #include
- #include
- #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;
- }
来源: http://www.bubuko.com/infodetail-3015457.html