题目链接:http://nyoj.top/problem/1251

  • 内存限制:64MB 时间限制:1000ms

题目描述

某山区的孩子们上学必须经过一条凹凸不平的土路，每当下雨天，孩子们非常艰难。现在村里走出来的Dr. Kong决定募捐资金重新修建着条路。由于资金有限，为了降低成本，对修好后的路面高度只能做到单调上升或单调下降。

为了便于修路，我们将整个土路分成了N段，每段路面的高度分别A1，A2,….,An。由于将每一段路垫高或挖低一个单位的花费成本相同，修路的总费用与路面的高低成正比。

现在Dr. Kong希望找到一个恰好含N个元素的不上升或不下降序列B1，B2,….,Bn，作为修过的路路段的高度。要求：

| A1-B1| + | A2–B2| + ... + | An-Bn|------>最小

输入描述

第一行： K 表示有多少组测试数据。
接下来对每组测试数据：
第1行: N 表示整个土路分成了N段
第2~N+1行：A1 A2 ……AN 表示每段路面的高度
2≤k≤10 0≤Ai≤10000000 0≤N≤500 (i=1,…, N)
所有数据都是整数。数据之间有一个空格。
数据保证| A1-B1|+| A2-B2|+ ... +| An-Bn|的最小值不会超过1e9

输出描述

对于每组测试数据，输出占一行：| A1-B1|+| A2-B2|+ ... +| An-Bn|的最小值。

样例输入

2
7
1 3 2 4 5 3 9
5
8 6 5 6 2

样例输出

3
1

解题思路

题意:把一串序列变为一段连续不增，或者连续不减的最小花费。
思路:解题关键是要注意到不同的高度数并不多，无论使路段上升还是下降，总是可以调整到另一个已经存在的高度，使得结果最优。dp[i][j]代表第i个元素换为第j个值的前i个总的最小花费,可列出状态转移方程:
dp[i][j]=abs(a[i]-b[j])+ab,ab为转化为1~j间的最小花费;由于是单调不增或者单调不减，只需要升序降序下b数组就可以了.

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, a[505], b[505], dp[505][505];
int solve() {
    int min_;
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; i++) {
        min_ = inf;
        for (int j = 0; j < n; j++) {
            min_ = min(min_, dp[i][j]);
            dp[i + 1][j] = abs(b[j] - a[i]) + min_;
        }
    }
    min_ = inf;
    for (int i = 0; i < n; i++)
        min_ = min(min_, dp[n][i]);
    return min_;
}
int main() {
    int t, min_;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            b[i] = a[i];
        }
        sort(b, b + n);
        min_ = solve();
        reverse(b, b + n);
        min_ = min(min_, solve());
        printf("%d\n", min_);
    }
    return 0;
}