#P2856. *【动态规划:区间中间推】奶牛吃草[USACO05NOV] Grazing on the Run G
*【动态规划:区间中间推】奶牛吃草[USACO05NOV] Grazing on the Run G
【题意】
贝西走在一条笔直的道路上,处于道路上坐标为 的地方。她突然发现周围长着 棵非常新鲜的青草!
其中第 棵青草位于道路上坐标为 的地方。贝西每秒钟可以沿着道路的方向向前或向后移动一个坐标单位的距离。
只要移动到青草所在的地方,就可以一口吞掉青草,贝西的食速很快,吃草的时间可以不计。
作为吃货的贝西当然要吃光所有的青草。不过,青草太新鲜了,在被吞掉之前,暴露在道路上的每棵青草每秒种都会损失一单位的口感。
请你告诉贝西,该怎样来回跑动,才能在口感损失之和最小的情况下吃掉所有的青草。
【输入格式】
第一行:两个整数 和 ,,
第二行到 行:第 行有一个整数 ,
【输出格式】
单个整数:表示最小损失的口感之和
4 10
1
9
11
19
44
【解释】
先跑到 9,然后跑到 11,再跑到 19,最后到1