256310-15 飞机加油问题

2563   10-15 飞机加油问题

题目描述

F国际航空公司在世界范围有n个国际机场。第i 个国际机场到中心机场的距离为di ,i=1,…,n。从国际机场 j到国际机场 i的飞行费用为 w( ,j )= s + (dj - di2 ,s为地面加油费用。从任何国际机场飞往中心机场的飞机可以在任一国际机场加油后继续飞行。飞机加油问题要求确定从距中心机场最远的国际机场飞到中心机场的最少费用。

对于给定的n个国际机场到中心机场的距离d1 ,d2 ,…… , d n,以及地面加油费用 s,计算从距中心机场最远的国际机场飞到中心机场的最少费用。

输入格式:

输入数据第一行有2 个整数n 和s,表示有n个国际机场(不包括中心机场),地面加油费用s。接下来的1 行中每行有n个整数d1 ,d2 ,…… , d n,表示给定的n个国际机场到中心机场的距离。

输出格式:

将计算出的最小费用输出

输入样例 复制
5 10
1 3 6 7 10
输出样例 复制
64

说明

0
0
通过提交
时空限制1000ms/128mb
题目来源
评测方式在线评测
题目类型
难        度