題目鏈接

題目描述

SNJ位于HB省西部一片群峰聳立的高大山地，橫亙于A江、B水之間，方圓數(shù)千平方公里，相傳上古的神醫(yī)在此搭架上山采藥而得名。景區(qū)山峰均在海拔3000米以上，堪稱”華中屋脊”。SNJ是以秀綠的亞高山自然風光，多樣的動植物種，人與自然和諧共存為主題的森林生態(tài)區(qū)。

SNJ處于中國地勢第二階梯的東部邊緣，由大巴山脈東延的余脈組成中高山地貌，區(qū)內(nèi)山體高大，高低不平。 交通十分不便。

最近，HB省決定修一條從YC市通往SNJ風景區(qū)的高速公路。經(jīng)過勘測分析，途中需要經(jīng)過高度分別為H1，H2，……,Hn的N個山區(qū)。由于高低不平，除正常的修路開支外，每段還要多出高度差|Hi - Hi-1|*X萬元的斜坡費用。Dr. Kong 決定通過填高一些區(qū)域的高度來降低總的費用。當然填高也是需要一些費用的。每填高Y單位，需要付出Y2萬元費用。

你能否幫Dr. Kong做出一個規(guī)劃，通過部分填高工程改造，使得總的費用降下來。

輸入

第一行： T 表示以下有T組測試數(shù)據(jù) （ 1≤ T ≤8 ）

對每組測試數(shù)據(jù)，

第一行：N X （2 ≤ N ≤100，000 1≤ X ≤100）

第二行：N個整數(shù)，分別表示N個區(qū)域的高度Hi ( 1<=Hi<=100 , i=1…. n)

輸出

對每組測試數(shù)據(jù)，輸出占一行，一個整數(shù)，即經(jīng)過部分填高工程改造后的最少費用。

樣例輸入

1
5 2
2 3 5 1 4

樣例輸出

15

思路

題目給的山的高度小于100，枚舉每一座山的高度。dp數(shù)組記錄總花費。
到 i 個山 ， 高度為 j 時的花費 = 上一座山的花費 + 這座山的墊高費用 + 差值的費用：
dp[ i ] [ j ] = dp[i - 1] [k] + Δ j * Δ j + Δ(j - k) * x

AC

#include<bits/stdc++.h> #define N 100005 #define ll long long #define mem(a, b) memset(a, b, sizeof(a)); using namespace std; int inf = 0x3f3f3f3f; int dp[N][105], h[N]; int main () {// freopen("in.txt", "r", stdin);int t;scanf("%d", &t);while (t--) {int n, x;scanf("%d%d", &n, &x);for (int i = 1; i <= n; i++) {scanf("%d", &h[i]);}mem(dp, inf);// 枚舉第一座山的花費(只有墊高費)， 山最高為100for (int i = h[1]; i <= 100; i++) {dp[1][i] = (i - h[1]) * (i - h[1]);}// 枚舉其他山， 花費為 墊高 + 差值// 2 - n座山for (int i = 2; i <= n; i++) {// 枚舉山的高度for (int j = h[i]; j <= 100; j++) {// 枚舉前座山的高度for (int k = h[i - 1]; k <= 100; k++) {dp[i][j] = min(dp[i][j], (j - h[i]) * (j - h[i]) + abs(j - k) * x + dp[i - 1][k]);}}}int ans = inf;for (int i = h[n]; i <= 100; i++) {ans = min(ans, dp[n][i]);}printf("%d\n", ans);}return 0; }

總結

以上是生活随笔為你收集整理的第十一届河南省赛--山区修路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。