POJ 3666 Making the Grade

解法

aを昇順にするコストをdpで求める。

hはaを昇順にsortしたものとする
dp[i + 1][j] = iをh[j]としたときの最小コスト
iをh[j]とするためには、i - 1はh[k] (k <= j)である必要があるので、以下のようなdpを解けばよい
dp[i + 1][j] = min{dp[i][k] (k <= j)} + | a[i] - h[j] |

aを降順にするコストはaを反転して同じ処理を使うと楽

ソースコード

int min_ascending(const vector<int>& a, const vector<int>& h)
{
    const int n = a.size();
    const int inf = INT_MAX;
    static int dp[2048][2048];	// (pos, height)
    erep(i, n) rep(j, n)
	dp[i][j] = inf;

    dp[0][0] = 0;
    rep(i, n)
    {
	int min_cost = inf; // min{dp[i][k]; k <= j}
	rep(j, n)
	{
	    chmin(min_cost, dp[i][j]);
	    dp[i + 1][j] = min_cost + abs(a[i] - h[j]);
	}
    }

    int res = inf;
    rep(j, n)
	chmin(res, dp[n][j]);
    return res;
}
int main()
{
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    rep(i, n)
	scanf("%d", &a[i]);
    vector<int> h = a;
    sort(all(h));

    int res = min_ascending(a, h);
    reverse(all(a));
    chmin(res, min_ascending(a, h));
    printf("%d\n", res);
}