A straight dirt road connects two fields on FJ's farm, but it changes elevation more than FJ would like. His cows do not mind climbing up or down a single slope, but they are not fond of an alternating succession of hills and valleys. FJ would like to add and remove dirt from the road so that it becomes one monotonic slope (either sloping up or down). You are given N integers $A_1,\ldots,A_N$ $(1\leq N \leq 2,000)$ describing the elevation $(0\leq A_i\leq 1,000,000,000)$ at each of N equally-spaced positions along the road, starting at the first field and ending at the other. FJ would like to adjust these elevations to a new sequence $B_1, \ldots , B_N$ that is either nonincreasing or nondecreasing. Since it costs the same amount of money to add or remove dirt at any position along the road, the total cost of modifying the road is $|A_1 - B_1| + |A_2 - B_2| + \ldots + |A_N - B_N|$. Please compute the minimum cost of grading his road so it becomes a continuous slope. FJ happily informs you that signed 32-bit integers can certainly be used to compute the answer.

输入描述

  • Line 1: A single integer: N
  • Lines 2..N+1: Line i+1 contains a single integer elevation: $A_i$

输出描述

  • Line 1: A single integer that is the minimum cost for FJ to grade his dirt road so it becomes nonincreasing or nondecreasing in elevation.

输入样例:

7
1
3
2
4
5
3
9

输出样例:

3

题目分析

首先,分析题意: 我们要计算将此数列转换为非严格单调增或非严格单调减后与原数列的每项差值最小。那么需要计算两次(单调增、单调减)再取最小值。

以非严格单调增为例: 假设 f(i - 1) 为A[0~i - 1]修改为非严格单调增所需要的最小值, 那么对于 f(i): 如果 A[i] >= B[i - 1], 那么 B[i] = A[i] 为最优解。 如果 A[i] < B[i - 1] , 要使目标成立,那么 B[i] 一定等于 B[i - 1] ,有两种取值来源:

  • B[i] = B[i - 1]
  • 存在一个 j < i, 使得 B[j] = B[j + 1] = B[j + 2] = ··· = B[i - 1] = B[i] = Val

对于第二种取值来源,很显然 Val 的值为 {A[j], A[j + 1], ···, A[i - 1], A[i]} 的中位数。我们可以假设 i - j + 1 为奇数,那么 Val 属于集合{A[j], A[j + 1], ···, A[i - 1], A[i]}。

我们可以发现,在符合目标条件的情况下,集合B中的元素的值一定在集合A中存在。

我们可以得到状态转移方程: $$ f(i,j) = \min_{k < j} { f(i - 1, k) + |a[i] - b[k]| } $$

代码实现

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e3 + 10, INF = 0x7fffffff;

int n, a[N], ra[N], b[N];
int calc(int * a) {
    int dp[N][N], ans = INF;
    for(int i = 1; i <= n; ++i) {
        int minv = INF;
        for(int j = 1; j <= n; ++j) {
            minv = min(minv, dp[i - 1][j]);
            dp[i][j] = minv + abs(a[i] - b[j]);
            if(i == n) ans = min(ans, dp[i][j]);
        }
    }
    return ans;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        ra[n - i + 1] = a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    cout << min(calc(a), calc(ra));
    return 0;
}

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status