4027946_ac_47ms_236k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>

int n;
int dp[2][2000], h[2000], g[2000], ans;

int min(int a, int b)
{
	return a < b ? a : b; 
}

void solve() 
{
	std::sort(g, g + n);
    int i, j, p = 0;
    
    for (i = 0; i < n; i++)
	{
		dp[0][i] = h[0] <= g[i] ? 0 : h[0] - g[i];
	}
    for (i = 1; i < n; i++)
    {
		p = 1 - p;
        dp[p][0] = dp[1 - p][0] + abs(h[i] - g[0]);
        for (j = 1; j < n; j++)
		{
			dp[p][j] = min(dp[p][j - 1], dp[1 - p][j] + abs(h[i] - g[j]));
		}
    }
    
    for (i = 0; i < n; i++)
	{
		ans = min(ans, dp[p][i]);
	}
}
int main()
{
	int i;

    scanf("%d", &n);
    ans = 1 << 30;
    for (i = 0; i < n; i++)
	{ 
		scanf("%d", &h[i]);
		g[i] = h[i]; 
	}
    solve();    
    for (i = 0; i < n; i++) 
	{ 
		h[i] *= -1; 
		g[i] *= -1; 
	}
    solve();
    printf("%d", ans);
	return 0;
}