[AtCoder Grand Contest 032] D Rotation Sort（DP）

Problem

题目地址

Solution

对题目的操作进行一个转换：

• 每次可以花费 (A) 的代价将一个数向右移到任意一个位置

• 每次可以花费 (B) 的代价将一个数向左移到任意一个位置

设 (f[i,j]) 表示将 (1 sim i) 变为升序，且最后一个没有改变位置的元素是 (j) 的最小花费。

[f[i,j]=egin{cases}f[i-1,j]+A&a_i>j\f[i-1,j]+B&a_i<jend{cases} ]

[f[i,a_i] = min_{j<a_i}{ f[i,j] } ]

Code

Talk is cheap.Show me the code.

#include<bits/stdc++.h>
#define INF 1e18
#define int long long
using namespace std;
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
    return x * f;
}
const int N = 5007;
int n,A,B;
int a[N];
int f[N][N];
signed main()
{
	n = read(), A = read(), B = read();
	for(int i=1;i<=n;++i) a[i] = read();
	memset(f, 0x3f, sizeof(f));
	f[0][0] = 0;
	for(int i=1;i<=n;++i) {
		for(int j=0;j<=n;++j) {
			if(a[i] > j) {
				f[i][j] = min(f[i][j], f[i-1][j]+A);
				f[i][a[i]] = min(f[i][a[i]], f[i-1][j]);
			} else f[i][j] = min(f[i][j], f[i-1][j]+B);
		}
	}
	int ans = INF;
	for(int i=0;i<=n;++i) ans = min(ans, f[n][i]);
	printf("%lld
",ans);
    return 0;
}
/*
9 40 50
5 3 4 7 6 1 2 9 8

220
*/

Summary

多做题！