太原企业网站建设,网站推广方案范例,龙华网站的建设,企业建一个网站作者推荐
【动态规划】【状态压缩】【2次选择】【广度搜索】1494. 并行课程 II
本文涉及知识点
动态规划汇总
LeetCode:1883. 准时抵达会议现场的最小跳过休息次数
给你一个整数 hoursBefore #xff0c;表示你要前往会议所剩下的可用小时数。要想成功抵达会议现场#…作者推荐
【动态规划】【状态压缩】【2次选择】【广度搜索】1494. 并行课程 II
本文涉及知识点
动态规划汇总
LeetCode:1883. 准时抵达会议现场的最小跳过休息次数
给你一个整数 hoursBefore 表示你要前往会议所剩下的可用小时数。要想成功抵达会议现场你必须途经 n 条道路。道路的长度用一个长度为 n 的整数数组 dist 表示其中 dist[i] 表示第 i 条道路的长度单位千米。另给你一个整数 speed 表示你在道路上前进的速度单位千米每小时。 当你通过第 i 条路之后就必须休息并等待直到 下一个整数小时 才能开始继续通过下一条道路。注意你不需要在通过最后一条道路后休息因为那时你已经抵达会议现场。 例如如果你通过一条道路用去 1.4 小时那你必须停下来等待到 2 小时才可以继续通过下一条道路。如果通过一条道路恰好用去 2 小时就无需等待可以直接继续。 然而为了能准时到达你可以选择 跳过 一些路的休息时间这意味着你不必等待下一个整数小时。注意这意味着与不跳过任何休息时间相比你可能在不同时刻到达接下来的道路。 例如假设通过第 1 条道路用去 1.4 小时且通过第 2 条道路用去 0.6 小时。跳过第 1 条道路的休息时间意味着你将会在恰好 2 小时完成通过第 2 条道路且你能够立即开始通过第 3 条道路。 返回准时抵达会议现场所需要的 最小跳过次数 如果 无法准时参会 返回 -1 。
示例 1 输入dist [1,3,2], speed 4, hoursBefore 2 输出1 解释 不跳过任何休息时间你将用 (1/4 3/4) (3/4 1/4) (2/4) 2.5 小时才能抵达会议现场。 可以跳过第 1 次休息时间共用 ((1/4 0) (3/4 0)) (2/4) 1.5 小时抵达会议现场。 注意第 2 次休息时间缩短为 0 由于跳过第 1 次休息时间你是在整数小时处完成通过第 2 条道路。 示例 2 输入dist [7,3,5,5], speed 2, hoursBefore 10 输出2 解释 不跳过任何休息时间你将用 (7/2 1/2) (3/2 1/2) (5/2 1/2) (5/2) 11.5 小时才能抵达会议现场。 可以跳过第 1 次和第 3 次休息时间共用 ((7/2 0) (3/2 0)) ((5/2 0) (5/2)) 10 小时抵达会议现场。 示例 3 输入dist [7,3,5,5], speed 1, hoursBefore 10 输出-1 解释即使跳过所有的休息时间也无法准时参加会议。 提示 n dist.length 1 n 1000 1 dist[i] 105 1 speed 106 1 hoursBefore 107
动态规划
动态规划的状态
pre[j] 表示 跳过j次行驶前i条道路的最少时间。 dp[j] 表示 跳过j次行驶前i1条道路的最少时间。 不直接记录时间那样会有小数。 记录时间*speed 这样就是整数。
动态规划的转移方程
0 pre[j]%speed 刚好是整数数据无需跳过。 dp[j] min( pre[j] dist[i] 否则 { d p [ j 1 ] m i n ( , p r e [ j ] d i s t [ i ] ) 跳过 d p [ j ] m i n ( , p r e [ j ] / s p e e d ∗ s p e e d s p e e d d i s t [ i ] ) 不跳过 \begin{cases} dp[j1] min(,pre[j]dist[i]) 跳过 \\ dp[j] min(,pre[j]/speed*speed speed dist[i]) 不跳过\\ \end{cases} {dp[j1]min(,pre[j]dist[i])dp[j]min(,pre[j]/speed∗speedspeeddist[i])跳过不跳过
动态规划的初始状态
pre全为0。前置状态转移后置状态。
动态规划的转移方程
i从0到大。
动态规划的返回值
pre第一个小于等于hoursBefore 的下标。
代码
核心代码
class Solution {
public:int minSkips(vectorint dist, int speed, int hoursBefore) {m_c dist.size();vectorint pre(m_c 1);for (const auto d : dist){vectorint dp(m_c 1, m_iNotMay);for (int j 0; j m_c; j){if (0 pre[j] % speed){dp[j] min(dp[j], pre[j] d);continue;}dp[j] min(dp[j], pre[j] / speed * speed speed d);//不跳过if (j ! m_c){dp[j1] min(dp[j1], pre[j] d);}}pre.swap(dp);}for (int i 0; i pre.size(); i){if (pre[i] (long long)hoursBefore * speed){return i;}}return -1;}int m_c;const int m_iNotMay 2000000000;
};测试用例 templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){Assert(v1[i], v2[i]);}}int main()
{ vectorint dist;int speed, hoursBefore;{Solution sln;dist { 1, 3, 2 }, speed 4, hoursBefore 2;auto res sln.minSkips(dist, speed, hoursBefore);Assert(res,1);}{Solution sln;dist { 7, 3, 5, 5 }, speed 1, hoursBefore 10;auto res sln.minSkips(dist, speed, hoursBefore);Assert(res, -1);}
}2023年2月
class Solution { public: int minSkips(vector dist, int speed, int hoursBefore) { m_c dist.size(); vector pre(m_c 1, m_iNotMay); pre[0] 0; for (const auto i : dist) { vector dp(m_c 1, m_iNotMay); const double dCurTime ((double)i) / speed; for (int j 0; j m_c; j) { if (pre[j] m_iNotMay m_eps) { continue; } dp[j] min(dp[j], ceil(pre[j] - m_eps) dCurTime); dp[j 1] min(dp[j 1], pre[j] dCurTime); } pre.swap(dp); } for (int i 0; i pre.size(); i) { if (pre[i] hoursBefore m_eps) { return i; } } return -1; } int m_c; int m_iNotMay 1000 * 1000 * 1000; const double m_eps 1E-7; };
2023年2月第二版
class Solution { public: int minSkips(vector dist, int speed, int hoursBefore) { m_c dist.size(); vector iiDists; for (const auto i : dist) { iiDists.push_back((long long)i * speed); } vector pre(m_c 1, m_iNotMay); pre[0] 0; for (const auto i : iiDists) { vector dp(m_c 1, m_iNotMay); const long long llCurTime i / speed; for (int j 0; j m_c; j) { if (pre[j] m_iNotMay ) { continue; } const long long llNew (0 pre[j] % speed) ? pre[j] : (speed * (pre[j] / speed 1)); dp[j] min(dp[j], llNew llCurTime); dp[j 1] min(dp[j 1], pre[j] llCurTime); } pre.swap(dp); } for (int i 0; i pre.size(); i) { if (pre[i] hoursBefore*(long long) speed ) { return i; } } return -1; } int m_c; long long m_iNotMay 1000LL * 1000 * 100010001000;
}; 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业
。也就是我们常说的专业的人做专业的事。 | |如果程序是一条龙那算法就是他的是睛|
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
