例题分析与搜索算法

《例题分析与搜索算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、瑰丽华尔兹(NOI2005)?一个N行M列的矩阵，矩阵小的某些方格上堆放了一些家具，其他的则是空地。有一台钢琴在初始位置(xO,yO),并且可以在空地上滑动，但不能撞上家具或滑出舞厅。每个时刻，钢琴都会随着船体倾斜的方向向和邻的方格滑动一格，相邻的方格可以是向东、向西、向南或向北的。可以在某一吋刻对钢琴施加魔法，这样在这一时刻，钢琴就会停留在原地不动。现在知道每一时刻钢琴将要往什么方向移动,请你安排施加魔法的时间，使得钢琴移动的总距离最长。？我们对钢琴的移动趋势是按时间的区间来描述的，且从1开始计算时间，比如“在［1,3］时间里向东移动，［4,5］时间

2、里向北移动=一共有K个时间区间。(N,M<=200,K<=200)瑰丽华尔兹(NOI2005)?设F(i,x,y)表示保证“第i段时间区间结束后，钢琴停在坐标(x,y)”的情况下，最长能进行的滑动距离。并且定义：T(i)表示第i段时间区间的长度，D(i)表示第i段时间区间内的风向，1表示东，2表示西，3表示南，4表示北。F的转移方程是：？max{f(i?l,x,y?s)+s}D(i)=l?max{f(i?l,x,y+s)+s}D(i)=2?转移条件：y)=?f(i,x,?每个时间单位最多滑动一格，也就是滑动距离不能超过T(i),s<=

3、T(i)o?max{f(i?l,x?s,y)+s}D(i)=3?若在D(i)的反方向上(因为我们这里是利用前面的结果倒推，所以？max{f(i?l,x+s,y)+s}D(i)=4?是反方向)，离(x,y)最近的障碍物距离为E(x,y),贝Us<E(x,y)。因为钢琴不能经过障碍物所在的格子。并且不能出边界。瑰丽华尔兹(NOI2005)?边界条件：?f(0,x,y)=0f(0,x,y)=??f(0,x,y)=oox=x0Ay=y0xx0VyMyO?该算法的时间复杂度是O(n3k),我们需要进行优化。？由F的转移方程实际上是根据D(i)的不同而不同，

4、我们只着重分析D(i)的一种情况，就可以同理推出其他情况。不妨设D(i)=l.瑰丽华尔兹(NOI2005)当D(i)=l时，实际上我们可以一行一行地考虑如何求F值。f(i,x,y)=max{f(i?1,x,y?s)+s}=max{f(i?1,x,y?s)?(y?s)}+y事实上我们可以对每个y,求出和应的(y・s)的取值区间。随着y的增加，(y・s)的区间的左右边界都递增。这样我们可以用一个队列维护需要计算的状态。设a(k)=f(i-l,x,k)-k瑰丽华尔兹(NOI2005)维护一个元素值递减的序列P,满足P1<P2<P3<...&

5、lt;PmaPl>aP2>aP3>..・>aPm若当前的状态区间为［A,B］,有P1>=Ao［AB］在维护当前的状态区间［A,B］时，需要以下操作将aB插入队尾，若队尾apm<aB,则删除apm(因为可aaa以证明状态apm在以后永远不会用到)。直到队尾元索值大于aB为止。若队首Pl<A,则删除Pl；直到P1>=A%止。取出队首元素，即区间［A,B］的最大状态值。瑰丽华尔兹(NOI2005)?这样每个元素进队一次，出队一次。每次取最大值的操作复杂度是0(l)o?所以计算一行的复杂度就优化到了O(N)o?在

6、D(i)=2,3,4的时候也可以同样处理。？那么，整个算法的时间复杂度就优化到了0(N2k)。线性数据结构优化一一POJ3709?在实际解题屮，很多题并不满足四边形不等式,但是，很有可能满足其一半的性质？满足这种性质的动态规划模型很有可能（不等价）满足凸完全单调性？有关凸完全单调性的理论知识，由于过于复杂，这里不做介绍，大家可以参考《算法艺术与信息学竞赛》？这里以一道题为例，介绍如何用队列优化满足凸单调性的动态规划模型POJ3709K-AnonymousSequence?给定一个长度为n的序列｛An｝和数字k?你需要将该序列修改成一个新的序列，所做的操

7、作是，将该序列的某一项Ai减去任意一个止数。？修改后的序列｛Bn｝必须满足下面两个要求？它是一个非递减序列？它的任意一个元素｛Bi｝,该序列中都至少有k・l个元素与其相等POJ3709分析？？？？原始的动态规划方程是什么？原始模型哪里不尽人意，可能改进。无法直接看岀方法怎么办？从该题的算法，我们得到了什么？POJ3709总结？从该题，我们可以看出满足凸完全单调性的许多问题的解法。？虽然说该题的方法并不是那淳哂衅占靶裕?但是，它的推导方式和思想，对于大多数凸完全单调性动态规划体都适用。？如果大家难以接受，对凸完全单调性的题，有O(nlgn)的，不太需要数

8、学推导的普及性方法，请查阅《算法艺术与信息学竞赛》搜索朵谈最困难也是最简单的算法搜索一一最苦难