1

これは標準的な動的プログラミングの質問LIS PROBLEMです

2D 座標のポイントの最長増加サブシーケンスが必要です

つまり、配列 のインデックス i にある 2 つの点 A(x1,y1) 、配列のインデックス j にある B(x2,y2) は、(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) で解くための任意のアルゴリズムを使用できますか?

参考までに、ここに何かを見つけました：

2 つの数値を含む最長増加部分列 (LIS)

私の場合は 2 番目の回答の方が適していますが、それをどのように実装できますか?

より良い答えまたはアルゴリズムが必要です。

4

1 に答える 1

1

両方の座標が範囲内にあると仮定し[0..N-1]ます (そうでない場合は、順序関係を変更せずに「圧縮」できます)。

標準の動的計画法ソリューションを詳しく見てみましょう。を番目f[i]の位置で終わる最長の増加サブシーケンスの長さとします。iそれを計算する単純な (しかし遅い) 方法は、前のすべての要素を繰り返し処理し、最適なものを選択することです。私たちが見つけたいのは、そのようなmax f[j]すべてのとです。長方形のある種の 2-D クエリのように見えます ( という別の条件があることは知っていますが、2 つの長方形と.をクエリすることで回避できます)。jp[j].x <= p[i].xp[j].y <= p[j].yp[j] != p[i](p[i].x - 1, p[i].y)(p[i].x, p[i].y - 1)

したがって、2 つの操作をサポートするデータ構造が必要です。特定の値を持つポイントを追加し、長方形の最大値を取得します。範囲内のすべてのポイントの y 座標によってバランスのとれた二分探索ツリーを格納する 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)ツリー内のレベルであり、各ポイントはレベルごとに最大 1 回どこかで発生する可能性があります。

このソリューションはすでに要件を満たしていますが、コーディングがかなり難しいようです。少し単純化できます。2 つの「実行」を行うことができます。最初の実行では、セグメント ツリーの各ノードに入るクエリを保存するだけです (これまでのところ、追加の情報は保存していません)。これで、ノードで発生するすべての数値のベクトルと同じ長さのバイナリ インデックス ツリーを保持して、各プレフィックスの最小値を追跡し、効率的に取得できます (全体像: すべてを知っているという事実を使用しました)。バイナリ検索の代わりに、並べ替えられたベクトルとバイナリ インデックス ツリーの組み合わせを使用できるように、事前にクエリを実行します)。時間と空間の複雑さの分析は、上記と同じです。

簡単にまとめると、四角形での最大クエリと新しい点の効率的な挿入をサポートするデータ構造を使用して、動的計画法ソリューションでj固定されたものに最適なものを見つけて高速化し、 .iO(N^2)O(N log^2 N)

于 2017-01-08T19:43:55.057 に答える