李宇亮-神奇的K线

《李宇亮-神奇的K线》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、神奇的K线【算法分析】假设给出的序列是a。对于每个a[i]有3种决策，删除它、保留它或者修改它。很容易想到DP。可以先确定一个大致的状态为f[i][j]，含义为将a中前i个元素通过一系列操作对应到新序列中的前j个元素的最小代价。但是这有一个问题，无法确定新序列中第j个元素的确切值。一种解决方案是给状态添加一维。算法1：DP，状态f[i][j][k]表示原序列的前i个对应于新序列的前j个，并且新序列的第j个数是k。转移方程f[i][j][k]=min{f[i-1][j-1][k-p[j-1]](若a[i]=

2、k)，f[i-1][j-1][k-p[j-1]]+modify，f[i-1][j][k]+delete}。2时间复杂度O(nmax)，max表示数列可能的最大值。期望得分10~40。另一种解决方案是修改f[i][j]的含义，规定a中第i个元素被保留，得到新序列中第j个元素的最小代价。算法2：DP，状态f[i][j]（j≤i）表示新序列中保留a[i]，并且a[i]是新序列中的第j个元素的最小代价。状态转移：f[i][j]=min{f[i’][j’]+modify*(j-1-j’)+delete*((i-j)

3、-(i’-j’))}，其中j’

4、P，状态f[i][j]（j≤i）表示新序列中保留a[i]，并且a[i]是新序列中的第j个元素的情况下，原序列中最多能保留多少个元素。状态转移：f[i][j]=max{f[i’][j’]+1}，j1其中j’

5、新序列中是第j个元素，那么新序列j1中的第一个元素就是a[i]p[k]，设为first[i][j]。k1由于转移只发生在first相等的状态之间，据此可以得到算法4。算法4：将first不同的状态分开计算。这样在寻找前继状态时就不会找到大量first[i’][j’]≠first[i][j]的状态了。在first中的每种数个数都不多时效果较好。时间4复杂度O(n)，期望得分30~60。将f列成一个表格：j1234567i1234567图中灰色格子的状态是无用的。蓝色格子代表状态f[i][j]，能转移

6、到它的状态在红色区域中，可以发现红色格子组成一个平行四边形。据此，我们可以得到两种算法：算法5：还是将first不同的状态分开计算。按照优先(i-j)从小到大，(i-j)相同则j从小到大的顺序dp。这样在计算f[i][j]（蓝色格子）时，所有的前继状态（红色格子）都已经被算出，并且第j’列中已经被计算的状态f[i’][j’]都满足i’-j’≤i-j。对于同一列中已经被计算的状态，只需要保存最优的那个即可。这样在计算一个状态f[i][j]时，只需要扫一遍1~(j-1)列中的最优状态，取其中最优的即可；计算好

7、地f[i][j]后，再用它更新第j列的最优状态。这样转移的复杂度降为O(n)，总时间复3杂度降为O(n)，期望得分60。由于每次转移要找的列是1~(j-1)列，是连续的，所以可以用线段树来维护连续列2的最优状态。转移复杂度就降为O(logn)，总时间复杂度降为O(nlogn)，期望得分100。标程用的是这种算法。算法6：类似于算法5，不过按照优先j从小到大，j相同则i从大到小的顺序dp。定义斜线k为所有i-j=k的状态f[i][j]组成的状态集合。线段树维护的是每一条斜线上的最优状态。计算状态f[i][j

8、]时，只需要用斜线1~(i-j)中的最优状态来转移即2可。时间复杂度O(nlogn)，期望得分100。为什么还要将first不同的分开呢？因为如果一起做，那么对于每一个first都要开一个数组来记录最优状态，空间不够。其实还可以将状态f[i][j]的含义改为前(i+j)个，删除i个，留下（保留或修改）j个，并且第(i+j)个保留。这样转移的区域就从一个非矩形的平行四边形变成了一个矩形（如下图）。虽然和前面的状态是等价的，但是更