Как решить взвешенный выбор активности с использованием деревьев сегментов и двоичного поиска?
Дано N рабочих мест, где каждая работа представлена следующими тремя ее элементами.
1) Время начала
2) Время окончания.
3) Прибыль или стоимость, связанная.
Найдите подмножество работ с максимальной прибылью, чтобы в подмножестве не перекрывались две работы.
Я знаю решение динамического программирования, которое имеет сложность O(N^2) (близко к LIS, где мы должны просто проверить предыдущие элементы, с которыми мы можем объединить текущий интервал и взять интервал, объединение которого дает максимум до i-го числа. элемент). Это решение может быть улучшено до O(N*log N) с помощью бинарного поиска и простой сортировки!
Но мой друг говорил мне, что это можно решить даже с помощью деревьев сегментов и бинарного поиска! Я понятия не имею, где я собираюсь использовать дерево сегментов и как.??
Вы можете помочь?
По запросу, извините, не комментируется
То, что я делаю, это сортировка на основе начального индекса, сохранение максимального доступного значения до i в DP[i] путем слияния предыдущих интервалов и их максимального доступного значения!
void solve()
{
int n,i,j,k,high;
scanf("%d",&n);
pair < pair < int ,int>, int > arr[n+1];// first pair represents l,r and int alone shows cost
int dp[n+1];
memset(dp,0,sizeof(dp));
for(i=0;i<n;i++)
scanf("%d%d%d",&arr[i].first.first,&arr[i].first.second,&arr[i].second);
std::sort(arr,arr+n); // by default sorting on the basis of starting index
for(i=0;i<n;i++)
{
high=arr[i].second;
for(j=0;j<i;j++)//checking all previous mergable intervals //Note we will use DP[] of the mergable interval due to optimal substructure
{
if(arr[i].first.first>=arr[j].first.second)
high=std::max(high , dp[j]+arr[i].second);
}
dp[i]=high;
}
for(i=0;i<n;i++)
dp[n-1]=std::max(dp[n-1],dp[i]);
printf("%d\n",dp[n-1]);
}
int main()
{solve();return 0;}
РЕДАКТИРОВАТЬ: хотя мой рабочий код, наконец, занял у меня 3 часа, чтобы отладить его! Более того, этот код медленнее, чем бинарный поиск и сортировка, из-за большей константы и плохой реализации:P (просто для справки)
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<cstring>
#include<iostream>
#include<climits>
#define lc(idx) (2*idx+1)
#define rc(idx) (2*idx+2)
#define mid(l,r) ((l+r)/2)
using namespace std;
int Tree[4*2*10000-1];
void update(int L,int R,int qe,int idx,int value)
{
if(value>Tree[0])
Tree[0]=value;
while(L<R)
{
if(qe<= mid(L,R))
{
idx=lc(idx);
R=mid(L,R);
}
else
{
idx=rc(idx);
L=mid(L,R)+1;
}
if(value>Tree[idx])
Tree[idx]=value;
}
return ;
}
int Get(int L,int R,int idx,int q)
{
if(q<L )
return 0;
if(R<=q)
return Tree[idx];
return max(Get(L,mid(L,R),lc(idx),q),Get(mid(L,R)+1,R,rc(idx),q));
}
bool cmp(pair < pair < int , int > , int > A,pair < pair < int , int > , int > B)
{
return A.first.second< B.first.second;
}
int main()
{
int N,i;
scanf("%d",&N);
pair < pair < int , int > , int > P[N];
vector < int > V;
for(i=0;i<N;i++)
{
scanf("%d%d%d",&P[i].first.first,&P[i].first.second,&P[i].second);
V.push_back(P[i].first.first);
V.push_back(P[i].first.second);
}
sort(V.begin(),V.end());
for(i=0;i<N;i++)
{
int &l=P[i].first.first,&r=P[i].first.second;
l=lower_bound(V.begin(),V.end(),l)-V.begin();
r=lower_bound(V.begin(),V.end(),r)-V.begin();
}
sort(P,P+N,cmp);
int ans=0;
memset(Tree,0,sizeof(Tree));
for(i=0;i<N;i++)
{
int aux=Get(0,2*N-1,0,P[i].first.first)+P[i].second;
if(aux>ans)
ans=aux;
update(0,2*N-1,P[i].first.second,0,ans);
}
printf("%d\n",ans);
return 0;
}
1 ответ
high=arr[i].second;
for(j=0;j<i;j++)//checking all previous mergable intervals //Note we will use DP[] of the mergable interval due to optimal substructure
{
if(arr[i].first.first>=arr[j].first.second)
high=std::max(high, dp[j]+arr[i].second);
}
dp[i]=high;
Это можно сделать в O(log n) с сегментным деревом.
Прежде всего, давайте перепишем это немного. Максимум, который вы берете, немного сложен, потому что он берет максимум суммы, включающей оба i а также j, Но i постоянен в этой части, так что давайте его уберем.
high=dp[0];
for(j=1;j<i;j++)//checking all previous mergable intervals //Note we will use DP[] of the mergable interval due to optimal substructure
{
if(arr[i].first.first>=arr[j].first.second)
high=std::max(high, dp[j]);
}
dp[i]=high + arr[i].second;
Отлично, теперь мы свели задачу к определению максимума в [0, i - 1] из значений, которые удовлетворяют вашему if состояние.
Если бы у нас не было if, это было бы простое применение деревьев сегментов.
Теперь есть два варианта.
1. Разобраться с O(log V) время запроса и O(V) память для дерева сегментов
куда V максимальный размер конечной точки интервала.
Вы можете построить дерево сегментов, в которое вы вставляете интервальные начальные точки при перемещении i, Затем вы запрашиваете диапазон значений. Примерно так, где дерево сегментов инициализируется -infinity и размера O(V),
Update(node, index, value):
if node.associated_interval == [index, index]:
node.max = value
return
if index in node.left.associated_interval:
Update(node.left, index, value)
else:
Update(node.right, index, value)
node.max = max(node.left.max, node.right.max)
Query(node, left, right):
if [left, right] does not intersect node.associated_interval:
return -infinity
if node.associated_interval included in [left, right]:
return node.max
return max(Query(node.left, left, right),
Query(node.right, left, right))
[...]
high=Query(tree, 0, arr[i].first.first)
dp[i]=high + arr[i].second;
Update(tree, arr[i].first.first, dp[i])
2. Сокращение до O(log n) время запроса и O(n) память для дерева сегментов
Поскольку число интервалов может быть значительно меньше их длины, разумно подумать, что мы могли бы как-то лучше их кодировать, так что их длина также O(n), Действительно, мы можем.
Это включает в себя нормализацию ваших интервалов в диапазоне [1, 2*n], Рассмотрим следующие интервалы
8 100
3 50
90 92
Давайте нанесем их на линию. Они бы выглядели так:
3 8 50 90 92 100
Теперь замените каждый из них своим индексом:
1 2 3 4 5 6
3 8 50 90 92 100
И напишите ваши новые интервалы:
2 6
1 3
4 5
Обратите внимание, что они сохраняют свойства ваших начальных интервалов: одни и те же перекрываются, одни и те же включаются друг в друга и т. Д.
Это можно сделать с помощью сортировки. Теперь вы можете применить тот же алгоритм дерева сегментов, за исключением того, что вы объявляете дерево сегментов для размера 2*n,