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

  • 内存限制:128MB 时间限制:3000ms

题目描述

SNJ位于HB省西部一片群峰耸立的高大山地，横亘于A江、B水之间，方圆数千平方公里，相传上古的神医在此搭架上山采药而得名。景区山峰均在海拔3000米以上，堪称"华中屋脊"。SNJ是以秀绿的亚高山自然风光，多样的动植物种，人与自然和谐共存为主题的森林生态区。
SNJ处于中国地势第二阶梯的东部边缘，由大巴山脉东延的余脉组成中高山地貌，区内山体高大，高低不平。 交通十分不便。
最近，HB省决定修一条从YC市通往SNJ风景区的高速公路。经过勘测分析，途中需要经过高度分别为H1，H2，……,Hn的N个山区。由于高低不平，除正常的修路开支外，每段还要多出高度差|Hi - Hi-1|*X万元的斜坡费用。Dr. Kong 决定通过填高一些区域的高度来降低总的费用。当然填高也是需要一些费用的。每填高Y单位，需要付出Y^2万元费用。
你能否帮Dr. Kong做出一个规划，通过部分填高工程改造，使得总的费用降下来。

输入描述

第一行：T 表示以下有T组测试数据(1≤ T ≤8)
对每组测试数据,
第一行：N  X(2 ≤ N ≤100，000 1≤ X ≤100)
第二行：N个整数，分别表示N个区域的高度Hi(1<=Hi<=100,i=1…. n)

输出描述

对每组测试数据，输出占一行，一个整数，即经过部分填高工程改造后的最少费用。

样例输入

1
5 2
2 3 5 1 4

样例输出

15

解题思路

题意:给你一道高低不平的路，现在需要修路，修路需要算上高度差的花费，但是填高也需要费用，问修路的最小花费是多少。
思路:数组dp[i][j]表示第i座山高度为j的状态下，前i座山总的最少花费，dp[i][j]只和dp[i-1][k]相关，计算出第n座山在所有高度下的最小花费，其中最小值即为结果。
状态转移方程为:
dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(j - k) * x + (j - a[i]) * (j - a[i]));
好像NYOJ的数据加大了，老是时间超限，因为循环次数太多了，所以寄存器运行register起到了作用，register可以加快速度。

#include <bits/stdc++.h>
#define re register
using namespace std;
const int inf = 0x3f3f3f3f;
int dp[100005][105], a[100005];
int main() {
    int t, n, x;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &x);
        for (re int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        for (re int i = a[0]; i <= 100; i++)
            dp[0][i] = (i - a[0]) * (i - a[0]);//第一段没有高度差的费用，只有填高费
        for (re int i = 1; i < n; i++) {//当前的每一段路高
            for (int j = a[i]; j <= 100; j++) {//当前路的高度
                dp[i][j] = inf;
                for (re int k = a[i - 1]; k <= 100; k++)//当前路的前一段路的高度
                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(j - k) * x);//找出最优的路的花费
                dp[i][j] += (j - a[i]) * (j - a[i]);//算上填高费
            }
        }
        int min_ = inf;
        for (re int i = a[n - 1]; i <= 100; i++)
            min_ = min(min_, dp[n - 1][i]);
        printf("%d\n", min_);
    }
    return 0;
}