codeforces|CF13C Sequence

大概的题意就是每次可以对一个数加一或者减一，然后用最小的代价使得原序列变成不下降的序列。

因为是最小的代价，所以到最后的序列中的每个数字肯定在原先的序列中出现过。（大家可以想一下到底是为什么，或者简单举几个例子验证一下）

我们用一个c数组拷贝原先的a数组，然后进行从小到大排序。

那么之后我们考虑DP，因为是5000的数据，考虑\(n^2\)做法。设\(dp[i][j]\)表示前i个已经符合要求，而且最大数不大于原序列第j个元素最小需要的代价。

那么我们可以得出转移方程\(dp[i][j]=min(dp[i][j-1],dp[i-1][j]+abs(a[i]-c[j])\)

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define MAXN 5010

using namespace std;

int n;

long long ans=(long long)1e18;

long long a[MAXN],c[MAXN],dp[2][MAXN];

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%I64d",&a[i]);

	memcpy(c,a,sizeof(a));

	sort(&c[1],&c[n+1]);

	memset(dp,0x3f,sizeof(dp));

	for(int i=1;i<=n;i++) dp[0][i]=0;

	for(int i=1;i<=n;i++)

	{

		for(int j=1;j<=n;j++)

			dp[1][j]=min(dp[1][j-1],dp[0][j]+abs(a[i]-c[j]));

		swap(dp[1],dp[0]);

	}

	for(int i=1;i<=n;i++) ans=min(ans,dp[0][i]);

	cout<<ans<<endl;

	return 0;

}

巴特西

codeforces|CF13C Sequence

最新文章

热门文章