我们把所有点放在数轴上，显然这些点被k点分为两各部分，不妨设这左右两部分为b[N],c[N],并用b[i].len表示左边各点到k点距离，用c[j].len表示右边各个点到k点距离，b[i].t和c[j].t表示该点最晚到达时间，然后b[N],c[N]分别按到k点距离排序，这样我们得到两组数据，再对
展开全文
C.张老师的旅行 链接：https://ac.nowcoder.com/acm/contest/5477/C 题目描述 张老师到了一个王国去旅游，王国有n个景点，张老师到达这个城市所在的车站恰好位于第x个景点，这个王国非常特别，恰好所有著名的景点都在分布在直线上，每个景点在坐标p
展开全文
观察发现，在最少时间的前提下走过的点必然是连续的区间设为[l,r]，那么唯一的变化就是终点落在l还是人r，这样我们可以通过dp来解决，我们设状态f[l][r][0]表示终点落在l的前提下走完区间[l,最小时间，f[l][r][1]同理终点落在r上，状态转移为：f[l-1][r][0]=min(f[l
展开全文
题意 n个点在数轴上排列，从其中一个点出发。每个点都有要求的最晚到达时间，问能否全部准时到达，如果能，给出完成时间。 分析 题目给出的n个景点是按照位置信息升序排列的。 把起始点，即t为0的点设为k，所有的点分成了两部分：k点左边的点和k点右边的点。 我们用一个数组dp[i][j][f]表示完成
展开全文
C、张老师的旅行 区间dp，动态规划众多模型中的一种，解决区间问题上有广泛的应用。基本思想就是一重循环枚举长度，还要一重循环枚举起点，终点就已经确定。关于决策点根据题目是否需要枚举或者优化成记录这里不展开。本题不需要枚举决策点，因为老师需要花费时间最短一定是从区间这一边一直走到另一边。 那么我们根据
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
