作者推荐
视频算法专题
本文涉及知识点
动态规划汇总
C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
LCP 57. 打地鼠
勇者面前有一个大小为3*3 的打地鼠游戏机,地鼠将随机出现在各个位置,moles[i] = [t,x,y] 表示在第 t 秒会有地鼠出现在 (x,y) 位置上,并于第 t+1 秒该地鼠消失。
勇者有一把可敲打地鼠的锤子,初始时刻(即第 0 秒)锤子位于正中间的格子 (1,1),锤子的使用规则如下:
锤子每经过 1 秒可以往上、下、左、右中的一个方向移动一格,也可以不移动
锤子只可敲击所在格子的地鼠,敲击不耗时
请返回勇者最多能够敲击多少只地鼠。
注意:
输入用例保证在相同时间相同位置最多仅有一只地鼠
示例 1:
输入: moles = [[1,1,0],[2,0,1],[4,2,2]]
输出: 2
解释: 第 0 秒,锤子位于 (1,1) 第 1 秒,锤子移动至 (1,0) 并敲击地鼠 第 2 秒,锤子移动至 (2,0) 第 3 秒,锤子移动至 (2,1) 第 4 秒,锤子移动至 (2,2) 并敲击地鼠 因此勇者最多可敲击 2 只地鼠
示例 2:
输入:moles = [[2,0,2],[5,2,0],[4,1,0],[1,2,1],[3,0,2]]
输出:3
解释: 第 0 秒,锤子位于 (1,1) 第 1 秒,锤子移动至 (2,1) 并敲击地鼠 第 2 秒,锤子移动至 (1,1) 第 3 秒,锤子移动至 (1,0) 第 4 秒,锤子在 (1,0) 不移动并敲击地鼠 第 5 秒,锤子移动至 (2,0) 并敲击地鼠 因此勇者最多可敲击 3 只地鼠
示例 3:
输入:moles = [[0,1,0],[0,0,1]]
输出:0
解释: 第 0 秒,锤子初始位于 (1,1),此时并不能敲击 (1,0)、(0,1) 位置处的地鼠
提示:
1 <= moles.length <= 105
moles[i].length == 3
0 <= moles[i][0] <= 109
0 <= moles[i][1], moles[i][2] < 3
动态规划
容易想到的解法:
moles排序
pre[j] 记录moles[i-1][0]时 锤子在j时,敲到的最多地鼠。
dp[i] 记录moles[i][0]时 锤子在j时,敲到的最多地鼠。
本文讲解另外一种解法。
动态规划的状态表示
moles排序,dp[i]记录敲到mole[i][0]的那只老鼠时,最多敲到的地鼠数。
动态规划的转移方程
j是前一只被敲到的地鼠,因为最多距离4,所以时间相差4就一定能敲倒。
情况一:
情况二:dp[i] = 1+max(iMax,
由于同一时间同一地点不会有两只地鼠,所以情况二,顶多只有三个,每个时间9个位置,共27种可能。
情况一,可以用前缀和,总时间复杂度是O(n)。
情况三:没有j,只敲到一只地鼠。
动态规划的初始状态
dp[0] =(0==modes[0][0]):1:0
动态规划的填表顺序
按时间顺序。
动态规划的返回值
dp的最大值。
代码
template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
*seft = max(*seft, other);
}
class Solution {
public:
int getMaximumNumber(vector<vector<int>>& moles) {
m_c = moles.size();
sort(moles.begin(), moles.end());
vector<int> dp(m_c);
int iMax = 0;
auto Can = [&](int i, int preTime, int x, int y)
{
const int dis = abs(moles[i][1] - x) + abs(moles[i][2] - y);
return moles[i][0] - preTime >= dis;
};
for (int i = 0, j = 0; i < m_c; i++)
{
while (moles[i][0] - moles[j][0] >= 4)
{
iMax = max(iMax, dp[j++]);
}
if (Can(i, 0, 1, 1))
{
MaxSelf(&dp[i],1 );
}
if (j > 0)
{
MaxSelf(&dp[i], iMax + 1);
}
for (int t = i-1 ; t >= j ;t--)
{
if (0 == dp[t])
{
continue;
}
if (Can(i, moles[t][0], moles[t][1], moles[t][2]))
{
MaxSelf(&dp[i], dp[t] + 1);
}
}
}
return *std::max_element(dp.begin(), dp.end());
}
int m_c;
};
测试用例
template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
vector<vector<int>> moles;
{
Solution sln;
moles= { {1,1,0},{2,0,1},{4,2,2} };
auto res = sln.getMaximumNumber(moles);
Assert(2, res);
}
{
Solution sln;
moles = { {2,0,2},{5,2,0},{4,1,0},{1,2,1},{3,0,2} };
auto res = sln.getMaximumNumber(moles);
Assert(3, res);
}
{
Solution sln;
moles = { {2,0,2},{6,2,0},{4,1,0},{2,2,2},{3,0,2} };
auto res = sln.getMaximumNumber(moles);
Assert(2, res);
}
{
Solution sln;
moles = { {0,1,0},{0,0,1} };
auto res = sln.getMaximumNumber(moles);
Assert(0, res);
}
{
Solution sln;
moles = { {0,1,0},{0,0,1},{0,2,1},{0,1,2},{0,0,2},{1,2,2},{1,0,0},{1,0,2},{2,0,2},{2,2,2},{2,0,1},{2,0,0},{2,2,0},{3,1,2},{3,0,0},{3,2,0},{3,0,2},{3,2,2},{3,1,0},{4,0,1},{4,1,2},{4,1,1},{4,0,2},{4,1,0},{5,0,1},{5,0,0},{5,2,0},{5,0,2},{6,1,2},{6,0,0},{6,0,2},{6,1,0},{6,2,1},{7,0,0},{7,2,0},{7,1,1},{7,1,2},{7,2,1},{8,2,2},{8,0,1},{8,2,1},{8,1,2},{8,1,1},{8,2,0},{9,1,1},{9,0,2},{9,2,2},{9,1,0},{9,2,1},{9,0,0},{9,2,0},{10,1,1},{10,0,2},{10,1,0},{10,2,2},{10,2,1},{10,1,2},{10,0,0} };
auto res = sln.getMaximumNumber(moles);
Assert(9, res);
}
}
2023年4月
class Solution {
public:
int getMaximumNumber(vector<vector>& moles) {
vector<vector<vector>> vMoves(5,vector<vector>(9));
for (int i = 0; i < 9; i++)
{
const int r = i / 3;
const int c = i % 3;
vector& v = vMoves[1][i];
if (r > 0)
{
v.emplace_back(i – 3);
}
if (r + 1 < 3)
{
v.emplace_back(i + 3);
}
if (c > 0)
{
v.emplace_back(i – 1);
}
if (c + 1 < 3)
{
v.emplace_back(i + 1);
}
v.emplace_back(i);
}
for (int iMove = 2; iMove <= 4; iMove++)
{
for (int iStatu = 0; iStatu < 9; iStatu++)
{
vector& v = vMoves[iMove][iStatu];
vector& vPre = vMoves[iMove – 1][iStatu];
for (int iPreStatu : vPre)
{
for (int iEndStatu : vMoves[1][iPreStatu])
{
v.emplace_back(iEndStatu);
}
}
v.insert(v.end(), vPre.begin(), vPre.end());
sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());
}
}
std::map<int, vector> mTimeStatu;
for (const auto& v: moles)
{
mTimeStatu[v[0]].emplace_back(v[1] * 3 + v[2]);
}
vector pre(9, -1000 * 1000);
int vHas[9] = { 0 };
for (const auto& iStatu : mTimeStatu[0])
{
vHas[iStatu] = 1;
}
pre[3 + 1] = vHas[4];
int iPreTime = 0;
for (const auto& it : mTimeStatu)
{
int iTime = min(4,it.first – iPreTime);
iPreTime = it.first;
//不移动
vector dp = pre;
memset(vHas, 0, sizeof(vHas));
for (const auto& iStatu :it.second)
{
vHas[iStatu] = 1;
}
for (int iCurStatu = 0; iCurStatu < 9; iCurStatu++)
{
const int iAdd = vHas[iCurStatu];
for (const int iPre : vMoves[iTime][iCurStatu])
{
dp[iCurStatu] = max(dp[iCurStatu], pre[iPre] + iAdd);
}
}
pre.swap(dp);
}
return *std::max_element(pre.begin(), pre.end());
}
};
扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。
版权声明:本文为博主作者:闻缺陷则喜何志丹原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/he_zhidan/article/details/136046235