力扣枚举位置【动态规划】【前缀和】【C++算法】LCP 57. 打地鼠

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总

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就一定能敲倒。情况一：

[

]

[

]

[

]

[

]

iMax=Max\Large_{j:0}^{moles[j][0]+4<=moles[i][0]}

iMax=Maxj:0moles[j][0]+4<=moles[i][0]dp[j] 情况二：dp[i] = 1+max(iMax,

[

]

[

]

[

]

[

]

\Large_{j:0}^{moles[j][0]+4> moles[i][0]}

j:0moles[j][0]+4>moles[i][0]如果能敲到dp[j]且dp[j]不为0$) 由于同一时间同一地点不会有两只地鼠，所以情况二，顶多只有三个,每个时间9个位置，共27种可能。情况一，可以用前缀和，总时间复杂度是O(n)。情况三：没有j，只敲到一只地鼠。

动态规划的初始状态

dp[0] =(0==modes[0][0]):1:0

动态规划的填表顺序

按时间顺序。

动态规划的返回值

dp的最大值。

代码

template

void MaxSelf(ELE* seft, const ELE& other)

{

*seft = max(*seft, other);

}

class Solution {

public:

int getMaximumNumber(vector>& moles) {

m_c = moles.size();

sort(moles.begin(), moles.end());

vector 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

void Assert(const T& t1, const T2& t2)

{

assert(t1 == t2);

}

template

void Assert(const vector& v1, const vector& 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> moles;

{

Solution sln;

moles= { {1,1,0},{2,0,1},{4,2,2} };