LIS для значений координат в O (NlogN) или O (Nlog ^ 2N)
Это стандартный вопрос динамического программирования ЛИС ПРОБЛЕМА
Я хочу самую длинную увеличивающуюся подпоследовательность для точек в 2D координатах
то есть 2 точки A (x1, y1) по индексу i в массиве, B (x2, y2) по индексу j в массиве могут быть частью возрастающей последовательности, если
(x1<= Х2) && (у1 <= У2) && ! (X1 == x2 && y1 == y2) && (J> я)
мой код, как показано ниже, который O (N ^ 2) с использованием стандартного DP: —
#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) с двумя числами
Второй ответ больше подходит для моего случая, но как мы можем это реализовать?
Нужен лучший ответ или алгоритм.
Решение
Я предполагаю, что обе координаты находятся в [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-координате, которое хранит сбалансированное двоичное дерево поиска по y-координате для всех точек в своем диапазоне, может сделать это в 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 для фиксированной i в O(N^2) динамическое программирование решение для его решения в O(N log^2 N),
Другие решения
Других решений пока нет …