福州企业网站,html模板网站模板下载,wordpress常用插件,网页设计师是前端吗作者推荐
【动态规划】【前缀和】【C算法】LCP 57. 打地鼠
本文涉及知识点
动态规划汇总
LeetCode2188. 完成比赛的最少时间
给你一个下标从 0 开始的二维整数数组 tires #xff0c;其中 tires[i] [fi, ri] 表示第 i 种轮胎如果连续使用#xff0c;第 x 圈需要耗时 fi…作者推荐
【动态规划】【前缀和】【C算法】LCP 57. 打地鼠
本文涉及知识点
动态规划汇总
LeetCode2188. 完成比赛的最少时间
给你一个下标从 0 开始的二维整数数组 tires 其中 tires[i] [fi, ri] 表示第 i 种轮胎如果连续使用第 x 圈需要耗时 fi * ri(x-1) 秒。 比方说如果 fi 3 且 ri 2 且一直使用这种类型的同一条轮胎那么该轮胎完成第 1 圈赛道耗时 3 秒完成第 2 圈耗时 3 * 2 6 秒完成第 3 圈耗时 3 * 22 12 秒依次类推。 同时给你一个整数 changeTime 和一个整数 numLaps 。 比赛总共包含 numLaps 圈你可以选择 任意 一种轮胎开始比赛。每一种轮胎都有 无数条 。每一圈后你可以选择耗费 changeTime 秒 换成 任意一种轮胎也可以换成当前种类的新轮胎。 请你返回完成比赛需要耗费的 最少 时间。 示例 1 输入tires [[2,3],[3,4]], changeTime 5, numLaps 4 输出21 解释 第 1 圈使用轮胎 0 耗时 2 秒。 第 2 圈继续使用轮胎 0 耗时 2 * 3 6 秒。 第 3 圈耗费 5 秒换一条新的轮胎 0 然后耗时 2 秒完成这一圈。 第 4 圈继续使用轮胎 0 耗时 2 * 3 6 秒。 总耗时 2 6 5 2 6 21 秒。 完成比赛的最少时间为 21 秒。 示例 2 输入tires [[1,10],[2,2],[3,4]], changeTime 6, numLaps 5 输出25 解释 第 1 圈使用轮胎 1 耗时 2 秒。 第 2 圈继续使用轮胎 1 耗时 2 * 2 4 秒。 第 3 圈耗时 6 秒换一条新的轮胎 1 然后耗时 2 秒完成这一圈。 第 4 圈继续使用轮胎 1 耗时 2 * 2 4 秒。 第 5 圈耗时 6 秒换成轮胎 0 然后耗时 1 秒完成这一圈。 总耗时 2 4 6 2 4 6 1 25 秒。 完成比赛的最少时间为 25 秒。 提示 1 tires.length 105 tires[i].length 2 1 fi, changeTime 105 2 ri 105 1 numLaps 1000
动态规划
ri大于2就算fi为1。20圈后用时就大于等于10^6不如换新轮胎只跑一圈。 一个轮胎跑i圈只需要考虑用时最短的那种轮胎。 轮胎圈数只需要考虑不到20种状态。
动态规划的状态表示
dp[j] 使用前i1种状态需要的最少时间包括换轮胎的时间。 时间复杂度O(numLaps 20)
动态规划的转移方程
dp[ji] min(,dp[j]useTime)
动态规划的初始值
dp[0] 0其它1e9。
动态规划的填表顺序
依次处理不到20种状态。
动态规划的返回值
dp.back()-changeTime
代码
核心代码
templateclass ELE,class ELE2
void MinSelf(ELE* seft, const ELE2 other)
{*seft min(*seft,(ELE) other);
}templateclass ELE
void MaxSelf(ELE* seft, const ELE other)
{*seft max(*seft, other);
}class Solution {
public:int minimumFinishTime(vectorvectorint tires, int changeTime, int numLaps) { vectorlong long vCurTireTime;for (const auto v : tires){ vCurTireTime.emplace_back(v[0]);}auto vTotalTireTime vCurTireTime;vectorlong long useTime { 0,*std::min_element(vCurTireTime.begin(),vCurTireTime.end()) };for(int q 2; q numLaps ;q ){for (int i 0 ; i vCurTireTime.size();i ){vCurTireTime[i] * tires[i][1];MinSelf(vCurTireTime[i], m_llNotMay);vTotalTireTime[i] vCurTireTime[i];MinSelf(vTotalTireTime[i], m_llNotMay);}const long long llMin *std::min_element(vTotalTireTime.begin(), vTotalTireTime.end());if (llMin (useTime[1] changeTime) * q){break;}useTime.emplace_back(llMin);}vectorlong long dp(numLaps 1, m_llNotMay);dp[0] 0;for (int i 1; i useTime.size(); i){for (int pre 0; pre dp.size(); pre){const int cur pre i;if (cur dp.size()){MinSelf(dp[cur], dp[pre] useTime[i] changeTime);}}}return (int)(dp.back()-changeTime);}const long long m_llNotMay 2e9;
};测试用例
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()
{ vectorvectorint tires;int changeTime, numLaps;{Solution sln;tires { {2,3},{3,4} }, changeTime 5, numLaps 4;auto res sln.minimumFinishTime(tires, changeTime, numLaps);Assert(res,21);}{Solution sln;tires { {1,10},{2,2},{3,4} }, changeTime 6, numLaps 5;auto res sln.minimumFinishTime(tires, changeTime, numLaps);Assert(res, 25);}{Solution sln;tires { {100000, 2}, { 10000,10000 }, { 1,2 }, { 1,10000 } }, changeTime 10000, numLaps 1000;auto res sln.minimumFinishTime(tires, changeTime, numLaps);Assert(res, 1085253);}{Solution sln;tires { {100000,2},{10000,10000},{1,2},{1,10000} }, changeTime 1, numLaps 1;auto res sln.minimumFinishTime(tires, changeTime, numLaps);Assert(res, 1);}}2023年2月
class Solution { public: int minimumFinishTime(vectorvector tires, int changeTime, int numLaps) { m_vNumLapUseMinTime.resize(20, m_iNotMay); for (const auto v : tires) { long long iNeedTime v[0]; int iPre 0; for (int j 0; j 20; j) { if (0 ! j) { iNeedTime iNeedTime*((long long)v[1]); } if (iNeedTime m_vNumLapUseMinTime[0] changeTime) { break; } iPre iNeedTime; m_vNumLapUseMinTime[j] min(m_vNumLapUseMinTime[j], (int)iPre); } } int iVilidNum 0; for (const auto i : m_vNumLapUseMinTime) { if (m_iNotMay ! i) { iVilidNum; } } vector dp(numLaps 1, m_iNotMay); dp[0] 0; for (int preNumLaps 0; preNumLaps numLaps; preNumLaps) { for (int j 0; j iVilidNum; j) { const int iNewNumLaps preNumLaps j 1; if (iNewNumLaps numLaps) { continue; } dp[iNewNumLaps] min(dp[iNewNumLaps], dp[preNumLaps] m_vNumLapUseMinTime[j] changeTime); } } return dp[numLaps] - changeTime; } vector m_vNumLapUseMinTime; const int m_iNotMay 1000 * 1000 * 1000; }; 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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**实现。
