题意 安排摆渡车出发的时间，使这些同学的等车时间之和最小。 分析 一 根据题意我们就有如下转移式子，令 $f_i$ 是以时间点 $i$ 为结尾的最小等车时间。那么 $$f_i = \min_{j\le i-m} \lbrace f_j+\sum_
展开全文
题目描述 有 n 名同学要乘坐摆渡车从人大附中前往人民大学，第 i 位同学在第 ti 分钟去 等车。只有一辆摆渡车在工作，但摆渡车容量可以视为无限大。摆渡车从人大附中出发、 把车上的同学送到人民大学、再回到人大附中(去接其他同学)，这样往返一趟总共花费 m 分钟(同学上下
展开全文
做法：记忆化搜索 思路： 1.小于等于当前时间点的人都要上车 2.当前时间没人就跳到下一个有人的时间点 3.考虑是不是要等待下一个人来再开车 #include <bits/stdc++.h>
using namespace std;
#define pb push_back
#def
展开全文
前言 作为NOIP-J的T3，这道题在一定程度上是会有区分度的。。。比如说这道题就有一堆解法： 剪枝优化状态 斜率优化DP 的神级DP 某位大佬说的算法但我这里就主要讲一下斜率优化DP吧，相信大部分都是这种做法吧 分析 我们考虑枚举设DP[i]表示在时回到人大附中的最少总时间Pre[i]表示及之
展开全文
摆渡车 题意 你可以操控一辆车的发车时间，你也知道跑一次往返的时间，你还知道每一个人到达车站的时间让你找到一种方案使得所有人的等待时间之和最少，求这个最小时间 分析 第一反应是把到达车站的人作为一个整体然后我们可以枚举最近的一次发车时间假设现在的时间是，最近的一次发车时间是那么从的等待时间可以表示为
展开全文
include<stdio.h> include using namespace std; const int maxn=502,maxm=102;const int INF=0x7fffffff; int f[maxn][maxm];int Min[maxn]; int a[maxn]
展开全文
Solution 中文的题意说的比较清楚，说下膜拜的大佬做法，大佬题解传送门 我们需要让整体学生等候时间最短，那么就要遵循几个原则。首先我们对到来时刻升序排序，依次处理。我们暴力搜索下去需要两个函数参数，搭载的人员数量和当前汽车回到起点所在时刻1、如果回来之后没有一个学生在等车，直接跳转到下一个需要
展开全文
思路:1.小于等于当前时间点的人都要上车2.当前时间没人就跳到下一个有人的时间点3.考虑是不是要等待下一个人来再开车参考代码如下: //100pts 500 100 4e6
#include<cstdio>
#include<algorithm>
#define INF 2
展开全文
观察到ttt很小，于是考虑在时间轴上dpdpdp。
设c[i]c[i]c[i]为在iii时刻出发的人数。
设dp[i]dp[i]dp[i]是在iii时刻出发，前iii分钟等待时间最少的值。
所以
dp[i]=j=1i−mdp[j]+∑k=j+1i(i−k)∗c[k]dp[i]= \min_{j=1}
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
