ZZNUOJ 2107 : 山区修路

  • 2018-06-05
  • 50
  • 0

题目:

SNJ位于HB省西部一片群峰耸立的高大山地,横亘于A江、B水之间,方圆数千平方公里,相传上古的神医在此搭架上山采药而得名。景区山峰均在海拔3000米以上,堪称”华中屋脊”。SNJ是以秀绿的亚高山自然风光,多样的动植物种,人与自然和谐共存为主题的森林生态区。

SNJ处于中国地势第二阶梯的东部边缘,由大巴山脉东延的余脉组成中高山地貌,区内山体高大,高低不平。 交通十分不便。

最近,HB省决定修一条从YC市通往SNJ风景区的高速公路。经过勘测分析,途中需要经过高度分别为H_1H_2,……,H_n的N个山区。由于高低不平,除正常的修路开支外,每段还要多出高度差|H_iH_i-1|*X万元的斜坡费用。Dr. Kong 决定通过填高一些区域的高度来降低总的费用。当然填高也是需要一些费用的。每填高Y单位,需要付出Y^2万元费用。

你能否帮Dr. Kong做出一个规划,通过部分填高工程改造,使得总的费用降下来。

Input:

第一行:T表示以下有T组测试数据( 1≤ T ≤8 )

对每组测试数据,

第一行:N X (2 ≤ N ≤100,000 1≤ X ≤100)

第二行:N个整数,分别表示N个区域的高度H_i(1<=H_i<=100,i=1…. n)

Output:

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

Sample Input:

1
5 2
2 3 5 1 4

Sample Output:

15

题目链接

2018第十一届河南省赛C动态规划题目,数组dp[i][j]表示第i座山高度为j的状态下,前i座山总的最少话费,dp[i][j]只和dp[i-1][k]相关,计算出第n座山在所有高度下的最小花费,其中最小值即为结果。

AC代码:

评论

还没有任何评论,你来说两句吧