http://poj.org/problem?id=3666

首先基于贪心的想法,变动后的数组中的元素只可能是原数组中的元素。

我们用a数组存原始数组,b数组存对a从小到大排序后的结果。
用dp[i][j]表示前i个元素的最后元素为原序列的第j小元素时的最优解,
则dp[i][j] = MIN{dp[i-1][k]} + abs(a[i]-b[j]) (0<=k<=j)
边循环边求MIN{dp[i-1][k]},同时用滚动数组优化,就可以在的时间复杂度和O(n)的空间复杂度下解决此题。

/*47ms,212KB*/

const int mx = 2005;

int a[mx], b[mx], dp[mx];

int main()
{
    int n, i, j, mindp;
    SI(n);
    For(i, n) SI(a[i]), b[i] = a[i];
    sort(b, b + n);
    For(i, n)
    {
        mindp = inf;
        For(j, n)
        {
            mindp = min(mindp, dp[j]);
            dp[j] = mindp + abs(b[j] - a[i]);
        }
    }
    PI(Min(dp, n));
    return 0;
}

Comments

comments powered by Disqus