POJ3666 & AcWing273 Making the Grade

题目链接

猜一波结论：新序列的数字一定都在原序列中出现过。证明

然后常规 dp 就好了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2000;
int a[N+10],t[N+10];
int dp[N+10][N+10];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	memcpy(t,a,sizeof(a));
	sort(t+1,t+n+1);
	int m=unique(t+1,t+n+1)-t-1;
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=m;i++) dp[0][i]=0;
	for(int i=1;i<=n;i++)
	{
		int Min=0x7fffffff;
		for(int j=1;j<=m;j++)
		{
			Min=min(Min,dp[i-1][j]);
			dp[i][j]=min(dp[i][j],Min+abs(t[j]-a[i]));
		}
	}
	int ans=0x7fffffff;
	for(int i=1;i<=m;i++) ans=min(ans,dp[n][i]);

	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=m;i++) dp[0][i]=0;
	for(int i=1;i<=n;i++)
	{
		int Min=0x7fffffff;
		for(int j=m;j;j--)
		{
			Min=min(Min,dp[i-1][j]);
			dp[i][j]=min(dp[i][j],Min+abs(t[j]-a[i]));
		}
	}
	for(int i=1;i<=m;i++) ans=min(ans,dp[n][i]);
	printf("%d",ans);
	return 0;
}