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;
}
