Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1505510
  • 博文数量: 399
  • 博客积分: 8508
  • 博客等级: 中将
  • 技术积分: 5302
  • 用 户 组: 普通用户
  • 注册时间: 2009-10-14 09:28
个人简介

能力强的人善于解决问题,有智慧的人善于绕过问题。 区别很微妙,小心谨慎做后者。

文章分类

全部博文(399)

文章存档

2018年(3)

2017年(1)

2016年(1)

2015年(69)

2013年(14)

2012年(17)

2011年(12)

2010年(189)

2009年(93)

分类: LINUX

2009-12-22 00:36:25

题目:
给出一个由n个数组成的序列x[1..n],找出它的最长单调上升子序列。即求最大的m和a1,
a2……,am,使得a1
这是一道动态规划的经典应用。一种动态规划的状态表示描述为:
m[i],1≤i≤n,表示以x[i]结尾的最长上升子序列的长度,则问题的解为 max{m[i],1≤i
≤n},状态转移方程和边界条件为:
m[i]=1+max{m[k]满足 x[k]
同时当m[i]>1时,令p[i]=k,表示最优决策,以便在计算出最优值后构造最长单调上升子序
列。
上述算法的状态总数为O(n),每个状态转移的状态数最多为O(n),每次状态转移的时间为
O(1),所以算法总的时间复杂度为O(n2)。

我们先来考虑以下两种情况:
1、若x[i] 的状态m[k] (k>j,k>i),必有x[k]>x[j]>x[i],则m[k]也能由m[i]转移得到;另一方面,
可以由状态m[i]转移得到的状态m[k] (k>j,k>i),当x[j]>x[k]>x[i]时,m[k]就无法由
m[j]转移得到。
由此可见,在所有状态值相同的状态中,只需保留最后一个元素值最小的那个状态即可。
2、若x[i]m[j],则m[j]这个状态不必保留。因为,可以由状态m[j]转移得到
的状态m[k] (k>j,k>i),必有x[k]>x[j]>x[i],则m[k]也能由m[i]转移得到,而且
m[i]>m[j],所以m[k]≥m[i]+1>m[j]+1,则m[j]的状态转移是没有意义的。
综合上述两点,我们得出了状态m[k]需要保留的必要条件:不存在i使得:x[i] m[i]≥m[k]。于是,我们保留的状态中不存在相同的状态值,且随着状态值的增加,最后一
个元素的值也是单调递增的。

也就是说,设当前保留的状态集合为S,则S具有以下性质D:
对于任意i∈S, j∈S, i≠j有:m[i]≠m[j],且若m[i] x[i]>x[j]。
下面我们来考虑状态转移:假设当前已求出m[1..i-1],当前保留的状态集合为S,下面计算
m[i]。
1、若存在状态k∈S,使得x[k]=x[i],则状态m[i]必定不需保留,不必计算。因为,不妨设
m[i]=m[j]+1,则x[j] 所以状态m[i]不需保留。
2、否则,m[i]=1+max{m[j]| x[j] x[j]=max{x[k]|x[k] 3、若2成立,则我们往S中增加了一个状态,为了保持S的性质,我们要对S进行维护,若存
在状态k∈S,使得m[i]=m[k],则我们有x[i]x[i], j∈S}。
于是状态k应从S中删去。
于是,我们得到了改进后的算法:
For i:=1 to n do
{
   找出集合S中的x值不超过x[i]的最大元素k;
   if   x[k]    {
       m[i]:=m[k]+1;
       将状态i插入集合S;
       找出集合S中的x值大于x[i]的最小元素j;
       if   m[j]=m[i]   then   将状态j从S中删去;
   }
}

从性质D和算法描述可以发现,S实际上是以x值为关键字(也是以m值为关键字)的有序集合
。若使用平衡树实现有序集合S,则该算法的时间复杂度为O(n*logn)。(每个状态转移的状
态数仅为O(1),而每次状态转移的时间变为O(logn))。也可以记录每个状态下的末尾最小值,

用二分法实现这个复杂度。

阅读(2062) | 评论(0) | 转发(1) |
1

上一篇:矩阵

下一篇:订票的贪心算法

给主人留下些什么吧!~~