当当当~
又到了解疑的时候啦~
今天给小伙伴们讲一下
摆渡车
首先我们来看一下题目
题目描述
有n名同学要乘坐摆渡车从人大附中前往人民大学，第i位同学在第ti分钟去等车。只有一辆摆渡车在工作，但摆渡车容量可以视为无限大。摆渡车从人大附中出发、把车上的同学送到人民大学、再回到人大附中（去接其他同学），这样往返一趟总共花费m分钟（同学上下车时间忽略不计）。摆渡车要将所有同学都送到人民大学。凯凯很好奇，如果他能任意安排摆渡车出发的时间，那么这些同学的等车时间之和最小为多少呢？
注意：摆渡车回到人大附中后可以即刻出发。
输入格式
第一行包含两个正整数n,m，以一个空格分开，分别代表等车人数和摆渡车往返一趟的时间。
第二行包含n个正整数，相邻两数之间以一个空格分隔，第i个非负整数ti代表第i个同学到达车站的时刻。
输出格式
输出一行，一个整数，表示所有同学等车时间之和的最小值（单位：分钟）。
输入样例1
51
输出样例1
0
输入样例2
55
输出样例2
4
说明/提示
同学1和同学4在第3分钟开始等车，等待0分钟，在第3分钟乘坐摆渡车出发。摆渡车在第4分钟回到人大附中。
同学2和同学3在第4分钟开始等车，等待0分钟，在第4分钟乘坐摆渡车出发。摆渡车在第5分钟回到人大附中。
同学5在第5分钟开始等车，等待0分钟，在第5分钟乘坐摆渡车出发。自此所有同学都被送到人民大学。总等待时间为0。
同学3在第1分钟开始等车，等待0分钟，在第1分钟乘坐摆渡车出发。摆渡车在第6分钟回到人大附中。
同学4和同学5在第5分钟开始等车，等待1分钟，在第6分钟乘坐摆渡车出发。摆渡车在第11分钟回到人大附中。
同学1在第11分钟开始等车，等待2分钟；同学2在第13分钟开始等车，等待0分钟。他/她们在第13分钟乘坐摆渡车出发。自此所有同学都被送到人民大学。总等待时间为4。
可以证明，没有总等待时间小于4的方案。
对于10%的数据，n≤10,m=1,0≤ti≤。
对于30%的数据，n≤20,m≤2,0≤ti≤。
对于50%的数据，n≤,m≤,0≤ti≤00。
另有20%的数据，n≤,m≤10,0≤ti≤4×0000。
对于%的数据，n≤,m≤,0≤ti≤4×0000。
解题思路
核心思路：动态规划
-dp[j][wn]表示第i个人开始，距离车到还有j分钟，这时候有wn个人在等。
-gap表示第i个人和第i+1个人之间的时间差
-状态转移方程:
当jgap时，dp[j][k]=dp[i+1][j-gap][k+1]+k*gap
当j=gap时，
dp[j][k]=min(dp[i+1][0][k+1]+k*gap,dp[i+1][max(0,j-gap+m)][1]+k*j)
下面是参考代码~
"#includebits/stdc++.h
usingnamespacestd;
intn,m,ti[],gap[];
intdp[][][];
intmain()
{
cinnm;
for(inti=1;i=n;++i)
cinti;
sort(ti+1,ti+1+n);
for(inti=1;in;++i)
gap=ti[i+1]-ti;
for(intk=1;k=n;++k)
for(intj=1;j=m;++j)
dp[n][j][k]=j*k;
for(inti=n-1;i=1;--i)
{
for(intk=1;k=i;++k)
{
for(intj=0;j=min(gap,m);++j)
{
dp[j][k]=min(dp[i+1][0][k+1]+gap*k,dp[i+1][max(0,m-gap+j)][1]+j*k);
}
for(intj=min(gap+1,m+1);j=m;++j)
{
dp[j][k]=dp[i+1][j-gap][k+1]+gap*k;
}
}
}
coutdp[1][0][1]endl;
return0;
}
"▼
点击了解更多详情
▼
成绩展示
喜报
CCFCSP-J/S第二轮认证评级，机房日子编程再创佳绩!
年NOI与NOIP获奖学员公示！新的一年我们再次出发！
机房课程
暑期课程
一对一课程，量身定制！
课程
线上一对一课程，为你量身定制!
搜索基础课程与动态规划基础课程
算法与数据结构专题课
NOIP数学专题课
《动态规划》特设专题课
机房解疑
机房解疑
数的划分
机房解疑
最长上升子序列
机房解疑
最小生成树(Prim算法)
机房解疑
杨辉三角形
机房解疑
迪杰斯特拉算法
机房解疑
Floyed(弗洛伊德)算法
机房解疑
哈密尔顿环
机房解疑
不等数列
机房解疑
记数问题
机房解疑
进制转换
机房解疑
四方定理
机房解疑
最大正方形
机房解疑
欧拉路
机房解疑
一元三次方程求解
机房解疑
装箱问题
机房解疑
均分纸牌
机房解疑
排队接水
机房解疑
货币系统
机房解疑
喝醉的狱卒
机房解疑
完全背包
机房解疑
01背包
机房解疑
合并石子（直线问题）
机房解疑
黑白棋子的移动
机房解疑
N皇后
机房解疑
逆序对
机房解疑
归并排序
机房解疑
快速排序
机房解疑
约瑟夫问题-猴子选大王
机房解疑
递归-汉诺塔问题
机房解疑
搜索-全排列
机房解疑
高精度运算，不简单的A+B
机房分享
机房分享
多省市高中特长生招生计划公布，注重“信息学特长生”选拔
机房分享
强基时代来了！知名中学纷纷开设“强基班”，是啥信号？
机房分享
信息学奥赛的10大误区
机房分享
送给NOIP竞赛学生的几条建议！
机房分享
五大学科竞赛到底能给我们带来什么？
机房分享
信息学奥赛（NOIP）复赛学习方法与备考攻略
机房分享
新手入门信息学奥赛（NOIP）常见问题解答
机房分享
高考数学再现编程题！
初赛专题
初赛专题
初赛中的数学知识
初赛专题
进制与编码
初赛专题
软件与操作系统信息安全网络
初赛专题
排列组合综合题
初赛专题
计算机基本常识与初赛真题选讲
扫描下方