3661 可以被机器人摧毁的最大墙壁数目 - 离散化线段树二分查找

正确解法

某个向右的机器人和某个向左的机器人射程重叠后。向右的机器人射程不变，向左的机器人缩短射程使之不重叠。向右射击仍然是一种状态，故只讨论向左。 令向左的机器人位于 x2，向左能射击到 x1。 则：射程非最大向左的最大值为 max_{x1}^{x2-1}(dp[x] + f(x))，其中 f(x) 是处于 x+1 ∼ x2 的墙数，令 g(x) 是 ≤ x 的墙数。 则 射程非最大向左的最大值为 max_{x1}^{x2-1}(dp[x] + g(x2) - g(x)) = g(x2) + max_{x1}^{x2-1}(dp[x] - g(x))。 我们用最大值线段树 maxTree2 记录：dp[x] - g(x)。 向左射击的最大值为：max(射程非最大向左的最大值，射程最大向左的最大值)。

向右也要枚举

比如：

robots = {3,5}, distance = {2,2}, walls = {4,6};

令向右的机器人在 x2，向右能射击到 x3。为了避免和前面的机器人重叠，我将此机器人的射程调整为：x+1 → x3。 则起点非 x2 向右的最大值为：max_{x:x2}^{x3-1} dp[x] + (x+1 ∼ x3) 的墙的个数 = g(x3) + max_{x:x2}^{x3-1}(dp[x] - g(x))。 可以共用：maxTree2。

内存超限代码

template<class TSave, class TRecord>
class CSingeUpdateLineTree {
protected:
    virtual void OnQuery(TSave& ans, const TSave& cur) = 0;
    virtual void OnUpdate(TSave& save, int iSave, const TRecord& update) = 0;
    virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) = 0;
};

template<class TSave, class TRecord>
class CVectorSingUpdateLineTree : public CSingeUpdateLineTree<TSave, TRecord> {
public:
    CVectorSingUpdateLineTree(int iEleSize, TSave tDefault)
        : m_iEleSize(iEleSize), m_save(iEleSize * 4, tDefault), m_tDefault(tDefault) {}
    void Update(int index, TRecord update) {
        Update(1, 0, m_iEleSize - 1, index, update);
    }
    TSave Query(int leftIndex, int leftRight, TSave tDefault) {
        TSave ans = tDefault;
        Query(ans, 1, 0, m_iEleSize - 1, leftIndex, leftRight);
        return ans;
    }
    TSave Query(int leftIndex, int leftRight) {
        return Query(leftIndex, leftRight, m_tDefault);
    }
    void Init(std::function<void(TSave&, const int&)> fun) {
        Init(fun, 1, 0, m_iEleSize - 1);
    }
    TSave QueryAll() { return m_save[1]; }
protected:
    int m_iEleSize;
    void Init(std::function<void(TSave&, const int&)> fun, int iNodeNO, int iSaveLeft, int iSaveRight) {
        if (iSaveLeft == iSaveRight) {
            fun(m_save[iNodeNO], iSaveLeft);
            return;
        }
        const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
        Init(fun, iNodeNO * 2, iSaveLeft, mid);
        Init(fun, iNodeNO * 2 + 1, mid + 1, iSaveRight);
        this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight);
    }
    void Query(TSave& ans, int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight) {
        if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) {
            this->OnQuery(ans, m_save[iNodeNO]);
            return;
        }
        if (iSaveLeft == iSaveRight) {
            return;
        }
        const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
        if (mid >= iQueryLeft) {
            Query(ans, iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight);
        }
        if (mid + 1 <= iQueryRight) {
            Query(ans, iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight);
        }
    }
    void Update(int iNodeNO, int iSaveLeft, int iSaveRight, int iUpdateNO, TRecord update) {
        if (iSaveLeft == iSaveRight) {
            this->OnUpdate(m_save[iNodeNO], iSaveLeft, update);
            return;
        }
        const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
        if (iUpdateNO <= mid) {
            Update(iNodeNO * 2, iSaveLeft, mid, iUpdateNO, update);
        } else {
            Update(iNodeNO * 2 + 1, mid + 1, iSaveRight, iUpdateNO, update);
        }
        this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight);
    }
    vector<TSave> m_save;
    const TSave m_tDefault;
};

template<class TSave, class TRecord>
class CTreeSingeLineTree : public CSingeUpdateLineTree<TSave, TRecord> {
protected:
    struct CTreeNode {
        int Cnt() const { return m_iMaxIndex - m_iMinIndex + 1; }
        int m_iMinIndex;
        int m_iMaxIndex;
        TSave data;
        CTreeNode* m_lChild = nullptr, *m_rChild = nullptr;
        ~CTreeNode() {
            delete m_lChild; m_lChild = nullptr;
            delete m_rChild; m_rChild = nullptr;
        }
    };
    CTreeNode* m_root;
    TSave m_tDefault;
public:
    CTreeSingeLineTree(int iMinIndex, int iMaxIndex, TSave tDefault) {
        m_tDefault = tDefault;
        m_root = CreateNode(iMinIndex, iMaxIndex);
    }
    void Update(int index, TRecord update) {
        Update(m_root, index, update);
    }
    TSave QueryAll() { return m_root->data; }
    TSave Query(int leftIndex, int leftRight) {
        TSave ans = m_tDefault;
        Query(ans, m_root, leftIndex, leftRight);
        return ans;
    }
    ~CTreeSingeLineTree() {
        delete m_root;
    }
protected:
    void Query(TSave& ans, CTreeNode* node, int iQueryLeft, int iQueryRight) {
        if ((node->m_iMinIndex >= iQueryLeft) && (node->m_iMaxIndex <= iQueryRight)) {
            this->OnQuery(ans, node->data);
            return;
        }
        if (1 == node->Cnt()) {
            return;
        }
        CreateChilds(node);
        const int mid = node->m_iMinIndex + (node->m_iMaxIndex - node->m_iMinIndex) / 2;
        if (mid >= iQueryLeft) {
            Query(ans, node->m_lChild, iQueryLeft, iQueryRight);
        }
        if (mid + 1 <= iQueryRight) {
            Query(ans, node->m_rChild, iQueryLeft, iQueryRight);
        }
    }
    void Update(CTreeNode* node, int iUpdateNO, TRecord update) {
        if ((iUpdateNO < node->m_iMinIndex) || (iUpdateNO > node->m_iMaxIndex)) {
            return;
        }
        if (1 == node->Cnt()) {
            this->OnUpdate(node->data, node->m_iMinIndex, update);
            return;
        }
        CreateChilds(node);
        Update(node->m_lChild, iUpdateNO, update);
        Update(node->m_rChild, iUpdateNO, update);
        this->OnUpdateParent(node->data, node->m_lChild->data, node->m_rChild->data, node->m_iMinIndex, node->m_iMaxIndex);
    }
    void CreateChilds(CTreeNode* node) {
        if (nullptr != node->m_lChild) {
            return;
        }
        const int iSaveLeft = node->m_iMinIndex;
        const int iSaveRight = node->m_iMaxIndex;
        const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
        node->m_lChild = CreateNode(iSaveLeft, mid);
        node->m_rChild = CreateNode(mid + 1, iSaveRight);
    }
    CTreeNode* CreateNode(int iMinIndex, int iMaxIndex) {
        CTreeNode* node = new CTreeNode;
        node->m_iMinIndex = iMinIndex;
        node->m_iMaxIndex = iMaxIndex;
        node->data = m_tDefault;
        return node;
    }
};

template<class TSave, class TRecord>
class CSetMaxLineTree : public CTreeSingeLineTree<TSave, TRecord> {
public:
    using CTreeSingeLineTree<TSave, TRecord>::CTreeSingeLineTree;
protected:
    virtual void OnQuery(TSave& ans, const TSave& cur) {
        ans = max(ans, cur);
    }
    virtual void OnUpdate(TSave& save, int iSave, const TRecord& updatee) {
        save = updatee;
    }
    virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) {
        par = max(left, r);
    }
};

class Solution {
public:
    int maxWalls(vector<int>& robots, vector<int>& distance, vector<int>& walls) {
        const int N = robots.size();
        const int M = (int)(1e9 + 2e5);
        sort(walls.begin(), walls.end());
        vector<pair<int, int>> rd;
        for (int i = 0; i < N; i++) {
            rd.emplace_back(robots[i], distance[i]);
        }
        sort(rd.begin(), rd.end());
        vector<int> vLeft(N), vRight(N);
        for (int i = 0; i < N; i++) {
            const auto& [pos, dis] = rd[i];
            const int iLeftRobot = i ? rd[i - 1].first : 1;
            vLeft[i] = max(iLeftRobot, pos - dis);
            const int iRightPos = (i + 1 == N) ? M : rd[i + 1].first;
            vRight[i] = min(iRightPos, pos + dis);
        }
        CSetMaxLineTree<int, int> maxTree(0, M, 0), maxTree2(0, M, -1000000);
        for (int i = 0; i < N; i++) {
            const int x1 = max(1, vLeft[i]), x2 = rd[i].first, x3 = min(M, vRight[i]);
            const int g2 = upper_bound(walls.begin(), walls.end(), x2) - walls.begin();
            const int g3 = upper_bound(walls.begin(), walls.end(), x3) - walls.begin();
            const int cnt1 = upper_bound(walls.begin(), walls.end(), x2) - lower_bound(walls.begin(), walls.end(), x1);
            const int left = maxTree.Query(0, x1 - 1) + cnt1;
            const int cnt2 = upper_bound(walls.begin(), walls.end(), x3) - lower_bound(walls.begin(), walls.end(), x2);
            const int right = maxTree.Query(0, x2 - 1) + cnt2;
            const int left2 = maxTree2.Query(x1, x2 - 1) + g2;
            const int right2 = maxTree2.Query(x2, x3 - 1) + g3;
            maxTree.Update(x2, max(left, left2));
            maxTree.Update(x3, max(right, right2));
            maxTree2.Update(x2, max(left, left2) - g2);
            maxTree2.Update(x3, max(right, right2) - g3);
        }
        return maxTree.QueryAll();
    }
};

空间超限的解决方法

一，离散化。 二，改用最大值树状数组。

核心代码

template<class T = int>
class CDiscretize {
public:
    CDiscretize(vector<T> nums) {
        sort(nums.begin(), nums.end());
        nums.erase(std::unique(nums.begin(), nums.end()), nums.end());
        m_nums = nums;
        for (int i = 0; i < nums.size(); i++) {
            m_mValueToIndex[nums[i]] = i;
        }
    }
    int operator[](const T value) const {
        auto it = m_mValueToIndex.find(value);
        if (m_mValueToIndex.end() == it) {
            return -1;
        }
        return it->second;
    }
    int size() const { return m_mValueToIndex.size(); }
    vector<T> m_nums;
protected:
    unordered_map<T, int> m_mValueToIndex;
};

template<class TSave, class TRecord>
class CSingeUpdateLineTree {
protected:
    virtual void OnQuery(TSave& ans, const TSave& cur) = 0;
    virtual void OnUpdate(TSave& save, int iSave, const TRecord& update) = 0;
    virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) = 0;
};

template<class TSave, class TRecord>
class CVectorSingUpdateLineTree : public CSingeUpdateLineTree<TSave, TRecord> {
public:
    CVectorSingUpdateLineTree(int iEleSize, TSave tDefault)
        : m_iEleSize(iEleSize), m_save(iEleSize * 4, tDefault), m_tDefault(tDefault) {}
    void Update(int index, TRecord update) {
        Update(1, 0, m_iEleSize - 1, index, update);
    }
    TSave Query(int leftIndex, int leftRight, TSave tDefault) {
        TSave ans = tDefault;
        Query(ans, 1, 0, m_iEleSize - 1, leftIndex, leftRight);
        return ans;
    }
    TSave Query(int leftIndex, int leftRight) {
        return Query(leftIndex, leftRight, m_tDefault);
    }
    void Init(std::function<void(TSave&, const int&)> fun) {
        Init(fun, 1, 0, m_iEleSize - 1);
    }
    TSave QueryAll() { return m_save[1]; }
protected:
    int m_iEleSize;
    void Init(std::function<void(TSave&, const int&)> fun, int iNodeNO, int iSaveLeft, int iSaveRight) {
        if (iSaveLeft == iSaveRight) {
            fun(m_save[iNodeNO], iSaveLeft);
            return;
        }
        const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
        Init(fun, iNodeNO * 2, iSaveLeft, mid);
        Init(fun, iNodeNO * 2 + 1, mid + 1, iSaveRight);
        this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight);
    }
    void Query(TSave& ans, int iNodeNO, int iSaveLeft, int iSaveRight, int iQueryLeft, int iQueryRight) {
        if ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) {
            this->OnQuery(ans, m_save[iNodeNO]);
            return;
        }
        if (iSaveLeft == iSaveRight) {
            return;
        }
        const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
        if (mid >= iQueryLeft) {
            Query(ans, iNodeNO * 2, iSaveLeft, mid, iQueryLeft, iQueryRight);
        }
        if (mid + 1 <= iQueryRight) {
            Query(ans, iNodeNO * 2 + 1, mid + 1, iSaveRight, iQueryLeft, iQueryRight);
        }
    }
    void Update(int iNodeNO, int iSaveLeft, int iSaveRight, int iUpdateNO, TRecord update) {
        if (iSaveLeft == iSaveRight) {
            this->OnUpdate(m_save[iNodeNO], iSaveLeft, update);
            return;
        }
        const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
        if (iUpdateNO <= mid) {
            Update(iNodeNO * 2, iSaveLeft, mid, iUpdateNO, update);
        } else {
            Update(iNodeNO * 2 + 1, mid + 1, iSaveRight, iUpdateNO, update);
        }
        this->OnUpdateParent(m_save[iNodeNO], m_save[iNodeNO * 2], m_save[iNodeNO * 2 + 1], iSaveLeft, iSaveRight);
    }
    vector<TSave> m_save;
    const TSave m_tDefault;
};

template<class TSave, class TRecord>
class CTreeSingeLineTree : public CSingeUpdateLineTree<TSave, TRecord> {
protected:
    struct CTreeNode {
        int Cnt() const { return m_iMaxIndex - m_iMinIndex + 1; }
        int m_iMinIndex;
        int m_iMaxIndex;
        TSave data;
        CTreeNode* m_lChild = nullptr, *m_rChild = nullptr;
        ~CTreeNode() {
            delete m_lChild; m_lChild = nullptr;
            delete m_rChild; m_rChild = nullptr;
        }
    };
    CTreeNode* m_root;
    TSave m_tDefault;
public:
    CTreeSingeLineTree(int iMinIndex, int iMaxIndex, TSave tDefault) {
        m_tDefault = tDefault;
        m_root = CreateNode(iMinIndex, iMaxIndex);
    }
    void Update(int index, TRecord update) {
        Update(m_root, index, update);
    }
    TSave QueryAll() { return m_root->data; }
    TSave Query(int leftIndex, int leftRight) {
        TSave ans = m_tDefault;
        Query(ans, m_root, leftIndex, leftRight);
        return ans;
    }
    ~CTreeSingeLineTree() {
        delete m_root;
    }
protected:
    void Query(TSave& ans, CTreeNode* node, int iQueryLeft, int iQueryRight) {
        if ((node->m_iMinIndex >= iQueryLeft) && (node->m_iMaxIndex <= iQueryRight)) {
            this->OnQuery(ans, node->data);
            return;
        }
        if (1 == node->Cnt()) {
            return;
        }
        CreateChilds(node);
        const int mid = node->m_iMinIndex + (node->m_iMaxIndex - node->m_iMinIndex) / 2;
        if (mid >= iQueryLeft) {
            Query(ans, node->m_lChild, iQueryLeft, iQueryRight);
        }
        if (mid + 1 <= iQueryRight) {
            Query(ans, node->m_rChild, iQueryLeft, iQueryRight);
        }
    }
    void Update(CTreeNode* node, int iUpdateNO, TRecord update) {
        if ((iUpdateNO < node->m_iMinIndex) || (iUpdateNO > node->m_iMaxIndex)) {
            return;
        }
        if (1 == node->Cnt()) {
            this->OnUpdate(node->data, node->m_iMinIndex, update);
            return;
        }
        CreateChilds(node);
        Update(node->m_lChild, iUpdateNO, update);
        Update(node->m_rChild, iUpdateNO, update);
        this->OnUpdateParent(node->data, node->m_lChild->data, node->m_rChild->data, node->m_iMinIndex, node->m_iMaxIndex);
    }
    void CreateChilds(CTreeNode* node) {
        if (nullptr != node->m_lChild) {
            return;
        }
        const int iSaveLeft = node->m_iMinIndex;
        const int iSaveRight = node->m_iMaxIndex;
        const int mid = iSaveLeft + (iSaveRight - iSaveLeft) / 2;
        node->m_lChild = CreateNode(iSaveLeft, mid);
        node->m_rChild = CreateNode(mid + 1, iSaveRight);
    }
    CTreeNode* CreateNode(int iMinIndex, int iMaxIndex) {
        CTreeNode* node = new CTreeNode;
        node->m_iMinIndex = iMinIndex;
        node->m_iMaxIndex = iMaxIndex;
        node->data = m_tDefault;
        return node;
    }
};

template<class TSave, class TRecord>
class CSetMaxLineTree : public CVectorSingUpdateLineTree<TSave, TRecord> {
public:
    using CVectorSingUpdateLineTree<TSave, TRecord>::CVectorSingUpdateLineTree;
protected:
    virtual void OnQuery(TSave& ans, const TSave& cur) {
        ans = max(ans, cur);
    }
    virtual void OnUpdate(TSave& save, int iSave, const TRecord& updatee) {
        save = max(save, updatee);
    }
    virtual void OnUpdateParent(TSave& par, const TSave& left, const TSave& r, int iSaveLeft, int iSaveRight) {
        par = max(left, r);
    }
};

class Solution {
public:
    int maxWalls(vector<int>& robots, vector<int>& distance, vector<int>& walls) {
        N = robots.size();
        Init(robots, distance, walls);
        CSetMaxLineTree<int, int> maxTree(M + 1, 0), maxTree2(M + 1, -1000000);
        for (const auto& [x1, x2, x3] : m_xs) {
            const int g2 = upper_bound(walls.begin(), walls.end(), x2) - walls.begin();
            const int g3 = upper_bound(walls.begin(), walls.end(), x3) - walls.begin();
            const int cnt1 = upper_bound(walls.begin(), walls.end(), x2) - lower_bound(walls.begin(), walls.end(), x1);
            const int left = maxTree.Query(0, x1 - 1) + cnt1;
            const int cnt2 = upper_bound(walls.begin(), walls.end(), x3) - lower_bound(walls.begin(), walls.end(), x2);
            const int right = maxTree.Query(0, x2 - 1) + cnt2;
            const int left2 = maxTree2.Query(x1, x2 - 1) + g2;
            const int right2 = maxTree2.Query(x2, x3 - 1) + g3;
            maxTree.Update(x2, max(left, left2));
            maxTree.Update(x3, max(right, right2));
            maxTree2.Update(x2, max(left, left2) - g2);
            maxTree2.Update(x3, max(right, right2) - g3);
        }
        return maxTree.QueryAll();
    }
    void Init(const vector<int>& robots, const vector<int>& distance, vector<int>& walls) {
        vector<pair<int, int>> rd;
        sort(walls.begin(), walls.end());
        auto tmp = walls;
        tmp.emplace_back(INT_MIN / 2);
        for (int i = 0; i < N; i++) {
            rd.emplace_back(robots[i], distance[i]);
            tmp.emplace_back(robots[i]);
        }
        CDiscretize<int> disc(tmp);
        for (auto& i : walls) {
            i = disc[i];
        }
        sort(rd.begin(), rd.end());
        for (int i = 0; i < N; i++) {
            const auto& [pos, dis] = rd[i];
            const int iLeftRobot = i ? rd[i - 1].first : 1;
            const int iLeft = max(iLeftRobot, pos - dis);
            const int iRightRobot = (i + 1 == N) ? (INT_MAX / 2) : rd[i + 1].first;
            const int iRight = min(iRightRobot, pos + dis);
            const int x1 = lower_bound(disc.m_nums.begin(), disc.m_nums.end(), iLeft) - disc.m_nums.begin();
            const int x2 = disc[pos];
            const int x3 = upper_bound(disc.m_nums.begin(), disc.m_nums.end(), iRight) - disc.m_nums.begin() - 1;
            m_xs.emplace_back(x1, x2, x3);
        }
        M = disc.m_nums.size();
    }
    int N, M;
    vector<tuple<int, int, int>> m_xs;
};

单元测试

vector<int> robots, distance, walls;
TEST_METHOD(TestMethod00) {
    robots = {4,10}, distance = {3,3}, walls = {6,7,8};
    auto res = Solution().maxWalls(robots, distance, walls);
    AssertEx(3, res);
}
TEST_METHOD(TestMethod01) {
    robots = {3,5}, distance = {2,2}, walls = {4,6};
    auto res = Solution().maxWalls(robots, distance, walls);
    AssertEx(2, res);
}
TEST_METHOD(TestMethod11) {
    robots = {4}, distance = {3}, walls = {1,10};
    auto res = Solution().maxWalls(robots, distance, walls);
    AssertEx(1, res);
}
TEST_METHOD(TestMethod12) {
    robots = {10,2}, distance = {5,1}, walls = {5,2,7};
    auto res = Solution().maxWalls(robots, distance, walls);
    AssertEx(3, res);
}
TEST_METHOD(TestMethod13) {
    robots = {1,2}, distance = {100,1}, walls = {10};
    auto res = Solution().maxWalls(robots, distance, walls);
    AssertEx(0, res);
}
TEST_METHOD(TestMethod14) {
    robots = {17,59,32,11,72,18}, distance = {5,7,6,5,2,10}, walls = {17,25,33,29,54,53,18,35,39,37,20,14,34,13,16,58,22,51,56,27,10,15,12,23,45,43,21,2,42,7,32,40,8,9,1,5,55,30,38,4,3,31,36,41,57,28,11,49,26,19,50,52,6,47,46,44,24,48};
    auto res = Solution().maxWalls(robots, distance, walls);
    AssertEx(37, res);
}
TEST_METHOD(TestMethod15) {
    robots = {31,22,4,43,8,38,5,15,35,37,27,42,40,28,20,21}, distance = {3,5,5,7,8,1,10,7,9,6,3,4,4,5,7,4}, walls = {34,74,54,46,79,89,7,73,12,27,44,5,62,43,60,71,10,63,41,77,33,91,32,53,66,51,78,18,61,6,8,24,23,81,3,25,40,85,84,15,52,48,17,59,55,64,50,21,88,36,2,16,80,69,22,87,1,28,65,31,83,26,67,72,29,75,57,9,30,86,39,37,13,19,56,68,35,90};
    auto res = Solution().maxWalls(robots, distance, walls);
    AssertEx(41, res);
}

简单版

性质一：如果机器人和墙挨着一起，此墙一定被摧毁。故只考虑不挨着机器人的墙。 性质二：由于子弹遇到机器人会停止，故墙只会被相邻的机器人摧毁。

动态规划的状态表示

dp0n 表示第 0 ∼ i 号机器人都已经射击完毕，且最后一个机器人向左（右) 射击能摧毁最后的墙数。 空间复杂度：O(n) 为了方便处理边界情况，增加一个机器人标兵，射击距离都是 0，位置分别在正负无穷大。

动态规划的填表顺序

n = 1 to N 枚举后继状态和选择。

动态规划的转移方程

如果 i-1 和 i 都向左射击，两者不会摧毁同一道墙。 如果 i-1 向右和 i 向左射击，两者可能摧毁同一道墙。需要出度重复。i 向右能够摧毁 g1 道墙，i-1 向左能够摧毁 g0 道墙，i 和 i-1 之间的机器人数量 c，则重复的墙数为：max(0, g1 + g0 - c)。 如果 i 向右射击，i-1 无论向左还是向右，两者都不会摧毁同一道墙。

动态规划的初始值

全为 0。

动态规划的返回值

max(dp0.back(), dp1.back())

代码

class Solution {
public:
    int maxWalls(vector<int>& robots, vector<int>& distance, vector<int>& walls) {
        const int N = robots.size();
        const int M = int(1e9 + 1e5 + 1);
        sort(walls.begin(), walls.end());
        vector<pair<int, int>> rd;
        for (int i = 0; i < N; i++) {
            rd.emplace_back(robots[i], distance[i]);
        }
        rd.emplace_back(INT_MIN / 2, 0);
        rd.emplace_back(INT_MAX / 2, 0);
        sort(rd.begin(), rd.end());
        vector<int> vLeft(N + 2), vRight(N + 2);
        for (int i = 0; i < rd.size(); i++) {
            const auto& [pos, dis] = rd[i];
            const int iLeftRobot = i ? rd[i - 1].first : -M;
            vLeft[i] = max(iLeftRobot, pos - dis - 1);
            const int iRightRobot = (i + 1 == N + 2) ? M : rd[i + 1].first;
            vRight[i] = min(iRightRobot, pos + dis + 1);
        }
        auto Cnt = [&](int left, int r) {
            int ans = lower_bound(walls.begin(), walls.end(), r) - upper_bound(walls.begin(), walls.end(), left);
            return ans;
        };
        //（left,r) 之间的墙数量，不包括 left,r。
        vector<int> dp0(N + 2), dp1(N + 2);
        for (int n = 1; n <= N; n++) {
            dp1[n] = max(dp0[n - 1], dp1[n - 1]) + Cnt(rd[n].first, vRight[n]);
            const int g = Cnt(vLeft[n], rd[n].first);
            dp0[n] = dp0[n - 1] + g;
            const int iRepeat = g + Cnt(rd[n - 1].first, vRight[n - 1]) - Cnt(rd[n - 1].first, rd[n].first);
            dp0[n] = max(dp0[n], dp1[n - 1] + g - max(0, iRepeat));
        }
        int cntSamePos = 0;
        for (const auto& pos : robots) {
            cntSamePos += Cnt(pos - 1, pos + 1);
        }
        return cntSamePos + max(dp0[N], dp1[N]);
    }
};