【动态规划】【前缀和】【C++算法】LCP 57. 打地鼠-阿里云开发者社区

【动态规划】【前缀和】【C++算法】LCP 57. 打地鼠

2024-02-27 33

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【动态规划】【前缀和】【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 <= 10⁵

moles[i].length == 3

0 <= moles[i][0] <= 10⁹

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

情况一：i M a x = M a x j : 0 m o l e s [ j ] [ 0 ] + 4 < = m o l e s [ i ] [ 0 ] 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,j : 0 m o l e s [ j ] [ 0 ] + 4 > m o l e s [ i ] [ 0 ] \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<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());

}

};