luogu2893 [USACO08FEB]修路Making the Grade

ref

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

typedef long long ll;

int n, m, a[2005], b[2005];

ll dp[2005][2005];

ll f(){

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

	dp[0][1] = 0;

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

		ll val=0x3f3f3f3f3f3f3f3f;

		for(int j=1; j<=m; j++){

			val = min(val, dp[i-1][j]);

			dp[i][j] = val + abs(a[i] - b[j]);

		}

	}

	ll re=0x3f3f3f3f3f3f3f3f;

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

		re = min(re, dp[n][i]);

	return re;

}

int main(){

	cin>>n;

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

		scanf("%d", &a[i]);

		b[i] = a[i];

	}

	sort(b+1, b+1+n);

	m = unique(b+1, b+1+n) - (b + 1);

	ll val=f();

	reverse(a+1, a+1+n);

	val = min(val, f());

	cout<<val<<endl;

	return 0;

}

巴特西

luogu2893 [USACO08FEB]修路Making the Grade

最新文章

热门文章