蜗牛

【问题描述】

一只蜗牛想要翻越n个电线杆,每个电线杆都有一定的高度,宽度可以忽略。蜗牛从最左边开始向右爬行,电线杆都在蜗牛右边。这只蜗牛力大无穷,它在一个电线杆下面时,便可以将这个电线杆推倒,但需要消耗一定的能量,而且蜗牛爬行的时候每走一单位也需要消耗一定的能量。现在需要你求蜗牛翻越n个电线杆消耗的最小能量。
注意,电线杆推倒后可能是如下情况

problem

【输入格式】

第一行两个正整数n,p,n表示电线杆的个数,p表示蜗牛移动一单位距离的耗能。
接下来n行,每行三个正整数xi,hi,wi(保证xi递增),xi表示该电线杆与蜗牛的距离,hi表示该电线的高度,wi表示推倒该电线杆需要消耗的能量。

【输出格式】

仅一个数,表示最小能量,保留3小数。

【题解】

递推?DP?

先预处理出每一根推倒后会倒在哪一根上

然后递推

注意精度问题

说点什么

您将是第一位评论人!

提醒
wpDiscuz