【算法笔记】双端处理

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法笔记】双端处理，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1916字，纯文字阅读大概需要3分钟。

内容图文

有的递推算法既可以从左向右推也可以从右向左推，这种特性赋予了我们一个技巧，双端处理法

当一个东西对递推数组的影响仅限于左半部分或右边部分，我们可以构造一个反向递推的数组，把不受影响的部分合起来计算

EX最大字段和

经典的最大子段和问题应该都很熟悉了，那么如果把这个问题魔改一下，选取两段不相交的子段，使得他们的和最大，该怎么做？

先回忆一下最大字段和的DP做法，记f[i]为以i为右端点的最大字段和，那么则可以从左向右递推出每一个f，问题解决

那么如果我们要选取两段，同时保证它们不相交，是不是可以选择f最大的两个点？

当然不行，这里出现了一个问题，你无法保证你选取的两个区间是不相交的，因为f数组只规定了右端点，而左端点是不确定的

我们希望找到一个方法，确保两个区间不相交

一个简单的做法就是再跑一边DP，记g[i]为以i为左端点的最大字段和

那么任选两点i,j(i<j)，以i为右端点的最大字段与以j为左端点的最大子段一定不相交

这样我们枚举i，对于每个i，找到max g[j] (j>i)，这样就可以在O(n)的时间内找到最大双子段和了(i要从n枚举到1，这样max g[j]就可以递推了)

EX清理石子

n堆石子排成一列，第i堆有a[i]颗石子，你每次可以在相邻的两堆中各取一颗石子，最终要把所有石子全部清除

当然，绝大多数情况下无法清除所有石子，幸好你有一项能力，在开始清理前，你可以交换任意两堆相邻的石子

请问你是否可以清理全部石子？(n<=1e5)

如果不考虑交换石子，那么这会是一道简单的题

先考虑最左端的石子，你想要清理它，就必须和第二堆一起清理，所以必须a[1]<=a[2]，否则无法全部清理

清理完第一堆以后，第二堆变成了实际上的"第一堆"，再用类似的方法清理它，以此类推

记f[i]为清理完[1,i-1]后，第i堆剩下的石子数，那么有解的充要条件就是所有f[i]>=0

下面考虑交换操作对f数组的影响

不难发现，交换操作只会影响f数组后面的一部分，如果你交换i和i+1，那么[1,i-1]不会受到影响

可以采用类似于EX最大字段和的方法，反着再来一个g数组，g[i]表示清理完[i+1,n]后第i堆剩下的石子数量(既然可以从左递推，那么也可以从有递推，因为清理第n堆石子也只有一种方法，和第n-1堆一起清理)

交换后i与i+1后先从左向右清理[1,i-1]再从右向左清理[i+2,n]，如果清理过后第i堆和第i+1堆石子数量相等，那么答案就是YES，否则可能需要交换另一对石子堆才行

内容总结

以上是互联网集市为您收集整理的【算法笔记】双端处理全部内容，希望文章能够帮你解决【算法笔记】双端处理所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---