Shu*_*rma 1 language-agnostic algorithm dynamic-programming segment-tree
给定N个工作,其中每个工作由以下三个元素表示.
1)开始时间
2)完成时间.
3)利润或价值相关.
找到作业的最大利润子集,使子集中没有两个作业重叠.
我知道一个动态编程解决方案,其复杂度为O(N ^ 2)(接近LIS,我们必须检查以前的元素,我们可以合并当前间隔并采用合并给出最大值的区间直到第i个这个解决方案可以使用二进制搜索和简单排序进一步改进为O(N*log N)!
但是我的朋友告诉我,甚至可以通过使用Segment Trees和二分搜索来解决它!我不知道我将在哪里使用Segment Tree以及如何使用.
你能帮我吗？
根据要求,抱歉没有评论
我正在做的是根据起始索引进行排序,通过合并先前的时间间隔和它们的最大可获得值,将最大可获得值存储到DP [i]中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;
}
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.