ACM模版

描述

题解

每次看到 dp 问题都能知道是 dp，可是就是反应不过来如何 dp。

这次也是这样，找了找题解，算是搞明白怎么 dp 了。

根据题意我们可以知道，不管怎么调整，我们都可以通过把路的高度调整为一个已有的高度来实现结果最优。所以我们可以设，dp[i][j] 表示考虑到第 i 段数路时，将其高度调整为第 j 高度时的最优解。这样就好了，代码很容易理解，直接看代码吧。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

const int MAXN = 520;
const int INF = 0x3f3f3f3f;

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

int main()
{
    int T;
    cin >> T;

    int n;
    while (T--)
    {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(dp, 0, sizeof(dp));

        cin >> n;
        for (int i = 0; i < n; i++)
        {
            scanf("%d", a + i);
            b[i] = a[i];
        }

        sort(b, b + n);
        for (int i = 0; i < n; i++)
        {
            int tmp = INF;
            for (int j = 0; j < n; j++)
            {
                for (int k = 0; k <= j; k++)
                {
                    tmp = min(tmp, dp[i][k]);
                }
                dp[i + 1][j] = tmp + abs(b[j] - a[i]);
            }
        }

        int res = INF;
        for (int i = 0; i < n; i++)
        {
            res = min(res, dp[n][i]);
        }

        reverse(a, a + n);
        for (int i = 0; i < n; i++)
        {
            int tmp = INF;
            for (int j = 0; j < n; j++)
            {
                for (int k = 0; k <= j; k++)
                {
                    tmp = min(tmp, dp[i][k]);
                }
                dp[i + 1][j] = tmp + abs(b[j] - a[i]);
            }
        }

        int res_ = INF;
        for (int i = 0; i < n; i++)
        {
            res_ = min(res_, dp[n][i]);
        }

        printf("%d\n", min(res, res_));
    }

    return 0;
}