国内今年初中生小朋友的noip普及组第三题大家试试看？

https://www.luogu.org/problemnew/show/P5017
一道不错的dp题。不过能在考场上做出来还是不太容易


题目描述

有nn 名同学要乘坐摆渡车从人大附中前往人民大学，第 ii 位同学在第 t_iti​ 分钟去 等车。只有一辆摆渡车在工作，但摆渡车容量可以视为无限大。摆渡车从人大附中出发、 把车上的同学送到人民大学、再回到人大附中（去接其他同学），这样往返一趟总共花费mm分钟（同学上下车时间忽略不计）。摆渡车要将所有同学都送到人民大学。

凯凯很好奇，如果他能任意安排摆渡车出发的时间，那么这些同学的等车时间之和最小为多少呢？

注意：摆渡车回到人大附中后可以即刻出发。

输入输出格式输入格式：

第一行包含两个正整数 n,mn,m，以一个空格分开，分别代表等车人数和摆渡车往返 一趟的时间。
第二行包含 nn 个正整数，相邻两数之间以一个空格分隔，第 ii 个非负整数 t_iti​ 代 表第 ii 个同学到达车站的时刻。

输出格式：

输出一行，一个整数，表示所有同学等车时间之和的最小值（单位：分钟）。

输入输出样例输入样例#1：

[size=1.2][url=]复制[/url]

5 1 3 4 4 3 5
输出样例#1：

[size=1.2][url=]复制[/url]

0

输入样例#2：

[size=1.2][url=]复制[/url]

5 5 11 13 1 5 5
输出样例#2：

[size=1.2][url=]复制[/url]

4

说明

【输入输出样例 1 说明】

同学 11 和同学 44 在第 33 分钟开始等车，等待 00 分钟，在第 33 分钟乘坐摆渡车出发。摆渡车在第 44 分钟回到人大附中。
同学 22 和同学 33 在第 44 分钟开始等车，等待 00 分钟，在第 44 分钟乘坐摆渡车 出发。摆渡车在第 55 分钟回到人大附中。
同学 55 在第 55 分钟开始等车，等待 00 分钟，在第 55 分钟乘坐摆渡车出发。自此 所有同学都被送到人民大学。总等待时间为 00。

【输入输出样例 2 说明】

同学 33 在第 11 分钟开始等车，等待 00 分钟，在第 11 分钟乘坐摆渡车出发。摆渡 车在第 66 分钟回到人大附中。
同学 44 和同学 55 在第 55 分钟开始等车，等待 11 分钟，在第 66 分钟乘坐摆渡车 出发。摆渡车在第 1111 分钟回到人大附中。
同学 11 在第 1111 分钟开始等车，等待 22 分钟；同学 22 在第 1313 分钟开始等车， 等待 00 分钟。他/她们在第 1313 分钟乘坐摆渡车出发。自此所有同学都被送到人民大学。 总等待时间为 44。
可以证明，没有总等待时间小于 44 的方案。

【数据规模与约定】
对于 10\%10% 的数据，n ≤ 10, m = 1, 0 ≤ t_i ≤ 100n≤10,m=1,0≤ti​≤100。
对于 30\%30% 的数据，n ≤ 20, m ≤ 2, 0 ≤ t_i ≤ 100n≤20,m≤2,0≤ti​≤100。
对于 50\%50% 的数据，n ≤ 500, m ≤ 100, 0 ≤ t_i ≤ 10^4n≤500,m≤100,0≤ti​≤104。
另有 20\%20% 的数据，n ≤ 500, m ≤ 10, 0 ≤ t_i ≤ 4 \times 10^6n≤500,m≤10,0≤ti​≤4×106。
对于 100\%100% 的数据，n ≤ 500, m ≤ 100, 0 ≤ t_i ≤ 4 \times 10^6n≤500,m≤100,0≤ti​≤4×106。