11282: 【原1282】修路

题目描述

author: Chen Xutong 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1282

Description

蹦蹦跳跳结束后，cxt回头看看自己走过的路坑坑洼洼的，心中非常不爽，他表示要把这段路的路面高度修成单调上升的或者单调下降的，整条路可以看成N段，N个整数A1，…..,An（1<=n<=2000）依次描述了每一段路的高度（0<=Ai<=1000000000）。希望找到一个恰好含N个元素的不上升或不下降的序列B1,……,Bn，作为修过的路中每个路段的高度。

由于将每一段路垫高或挖低一个单位消耗的体力相同，于是可以表示为：

|A1-B1|+|A2-B2|+…..+|An-Bn|

请你计算一下，要修好这段道路，最少消耗多少体力。消耗的总体力不会超过2^31-1

Input Format

输入文件的第一行仅有一正整数N，以下的N行每行一个整数Ai，表示路面的高度。

Output Format

输出文件仅有一个正整数，表示如果把路修成高度不上升或不下降的最小花费

Sample Input

Sample Output

Hint

将第一个高度为3的路段的高度减少为2，将第二个高度为3的路段的高度增加到5，总花费为|2-3|+|5-3|=3，并且各路段的高度为一个不下降序列 1,2,2,4,5,5,9。

ligongzzz's solution

#include "iostream"
#include "cmath"
#include "algorithm"
using namespace std;

int n, ans = 1e9, a[2009], c[2009], 
f[2009][2009], g[2009][2009];

void sol()
{
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            f[i][j] = g[i - 1][j] + abs(a[i] - c[j]);
            if (j == 1) 
                g[i][j] = f[i][j];
            else 
                g[i][j] = min(f[i][j], g[i][j - 1]);
        }
    }
    for (int i = 1; i <= n; ++i)
        ans = min(ans, f[n][i]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    //输入并排序
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        c[i] = a[i];
    }
    sort(c + 1, c + n + 1);

    sol();
    //反序
    for (int i = 1; i <= n / 2; ++i)
        swap(c[i], c[n - i + 1]);

    sol();
    cout << ans;

    return 0;
}

Neight99's solution

#include <cmath>
#include <iostream>

using namespace std;

const int maxN = 2000 + 100;

long long ans = 1e17, height[maxN] = {0}, height1[maxN] = {0},
          dp[maxN][maxN] = {0};

void qSort(long long *, int, int);
void DP(int);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> height[i];
        height1[i] = height[i];
    }
    qSort(height1, 0, n - 1);
    DP(n);
    cout << ans;

    return 0;
}

void qSort(long long *nums, int l, int h) {
    if (l >= h) {
        return;
    }
    int first = l, last = h;
    long long key = nums[first];

    while (first < last) {
        while (first < last && nums[last] >= key) {
            --last;
        }
        nums[first] = nums[last];
        while (first < last && nums[first] <= key) {
            ++first;
        }
        nums[last] = nums[first];
    }
    nums[first] = key;
    qSort(nums, l, first - 1);
    qSort(nums, first + 1, h);
}

void DP(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0) {
                if (j == 0) {
                    dp[i][j] = abs(height1[j] - height[i]);
                } else {
                    dp[i][j] = min(abs(height1[j] - height[i]), dp[i][j - 1]);
                }
            } else if (j == 0) {
                dp[i][j] = dp[i - 1][j] + abs(height1[j] - height[i]);
            } else {
                dp[i][j] = min(dp[i - 1][j] + abs(height1[j] - height[i]),
                               dp[i][j - 1]);
            }

            if (i == n - 1) {
                ans = min(ans, dp[i][j]);
            }
        }
    }

    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j < n; j++) {
            if (i == n - 1) {
                if (j == 0) {
                    dp[i][j] = abs(height1[j] - height[i]);
                } else {
                    dp[i][j] = min(abs(height1[j] - height[i]), dp[i][j - 1]);
                }
            } else if (j == 0) {
                dp[i][j] = dp[i + 1][j] + abs(height1[j] - height[i]);
            } else {
                dp[i][j] = min(dp[i + 1][j] + abs(height1[j] - height[i]),
                               dp[i][j - 1]);
            }

            if (i == 0) {
                ans = min(ans, dp[i][j]);
            }
        }
    }

    return;
}

WashSwang's solution

#include <iostream>
#include <cstring>
using namespace std;
int n,h[3000],o[3000];
long long dps[2001][2001],dpt[2001][2001],mins,mint;
void qsort(int *s,int *t){
    if (s+1>=t) return;
    int i=0,j=int(t-s)-1,x=s[0];
    while (i<j){
        while (i<j&&s[j]>=x) j--;
        if (i<j) s[i++]=s[j];
        while (i<j&&s[i]<=x) i++;
        if (i<j) s[j--]=s[i];
    }
    s[i]=x;
    qsort(s,s+i);
    qsort(s+i+1,t);
}
int main() {
    cin>>n;
    for (int i=1;i<=n;++i){
        cin>>h[i];
        o[i]=h[i];
    }
    qsort(o+1,o+n+1);
    for (int i=1;i<=n;++i) {
        mins=1e12;
        for (int j = 1; j <= n; ++j){
            if (dps[i-1][j]<mins) mins=dps[i-1][j];
            dps[i][j]=mins+abs(h[i]-o[j]);
        }
        mint=1e12;
        for (int j = n; j>=1;--j){
            if (dpt[i-1][j]<mint) mint=dpt[i-1][j];
            dpt[i][j]=mint+abs(h[i]-o[j]);
        }
    }
    mins=1e12;
    mint=1e12;
    for (int i=1;i<=n;++i)
    {
        mins=min(dps[n][i],mins);
        mint=min(dpt[n][i],mint);
    }
    cout<<min(mins,mint);
    return 0;
}