1

这是一个标准的动态规划问题LIS PROBLEM

我想要二维坐标中点的最长递增子序列

也就是说，数组中索引 i 处的 2 个点 A(x1,y1)，数组中索引 j 处的 B(x2,y2) 可以是递增序列的一部分 if (x1<=x2) && (y1 <=y2) && !(x1==x2 && y1==y2) && (j>i)

我的代码如下，使用标准 DP 为 O(N^2) ：-

#include <vector>
#include <iostream>
#include <algorithm>


using namespace std;


struct Pair
{
    int x;
    int y;
};



int main()
{

    int n;
    cin>>n;

    vector<Pair> arr;
    int L[1000000];

    Pair a;

    int i;int Maxchain=0;
    for(i=0;i<n;i++)
    {

        cin>>a.x>>a.y;
        arr.push_back(a);

        L[i]=0;
        for (int j = i-1; j >=0; j--)
        {

            if ((L[j]>(Maxchain-1))&&(L[j]>=L[i])&&(arr[j].x <= arr[i].x) && (arr[j].y <= arr[i].y) && !(arr[j].x == arr[i].x && arr[j].y == arr[i].y))
                L[i] = L[j]+1;


        }

                Maxchain = L[i]>Maxchain ?L[i]:Maxchain ;

    }
    cout<<Maxchain;

    return 0;
}

这是一个 O(N^2) 解决方案，是否可以进一步减少或任何算法来解决 O(NlogN) 或 O(Nlog^2N) ？

供参考在这里找到了一些东西：

具有两个数字的最长递增子序列 (LIS)

第二个答案更适合我的情况，但我们如何实施呢？

需要更好的答案或算法。

4

1 回答 1

1

我假设两个坐标都在[0..N-1]范围内（如果不是这样，我们可以“压缩”它们而不改变它们的排序关系）。

让我们仔细看看标准的动态规划解决方案。设是在第 - 位置f[i]结束的最长递增子序列的长度。i一种简单（但缓慢）的计算方法过于迭代所有先前的元素并选择最佳元素。我们想要找到的是max f[j]所有这样j的p[j].x <= p[i].x和p[j].y <= p[j].y。它看起来像是矩形中的某种二维查询（我知道还有另一个条件，但我们可以通过查询两个矩形和.p[j] != p[i]来解决它）。(p[i].x - 1, p[i].y)(p[i].x, p[i].y - 1)

所以我们需要一个支持两种操作的数据结构：添加具有特定值的点和获取矩形中的最大值。通过 x 坐标存储平衡二叉搜索树的 x 坐标分段树在其范围内的所有点上存储平衡的二叉搜索树，可以在O(log^2 N)每个查询中执行此操作。每个查询范围都被分解为O(log N)树中的最多节点。如果是插入查询，我们需要将当前点插入(p[i].x, p[i].y)到f[i]每个节点的二叉搜索树中。如果它是获取最大查询，我们需要为这些树中的每一个的某些前缀获取最大值。无论哪种方式，我们对每个查询执行一个二叉搜索树O(log N)操作。O(log N)因此，总时间复杂度为(N * log^2 N)。空间复杂度O(N log N)有O(log N)树中的级别，每个点在每个级别最多可以出现一次。

此解决方案已满足您的要求，但看起来很难编码。我们可以稍微简化一下。我们可以进行两次“运行”：在第一次运行期间，我们只存储进入分段树每个节点的查询（到目前为止，我们没有存储任何额外的信息）。现在我们可以保留节点中出现的所有数字的向量和相同长度的二叉索引树，以跟踪每个前缀的最小值并有效地获取它（大图：我们使用了我们知道所有事先查询，所以我们可以使用排序向量和二叉索引树的组合，而不是二叉搜索）。时间和空间复杂度分析同上。

简短回顾：我们使用了一种数据结构，该结构支持矩形中的最大查询和有效插入新点，以加快在动态规划解决方案中找到最佳j的固定值来解决它。iO(N^2)O(N log^2 N)

于 2017-01-08T19:43:55.057 回答