题目描述

塔子哥在玩一个消除游戏。这个消除游戏有点特别，游戏中，你会得到n个一维排列的有各自颜色的砖块。

题目思路

题目和经典的区间dp非常相似，没有接触过区间dp的可以先了解一下概念。

设f[l][r]表示区间l到r范围内的砖块全部消除的最大分数，转移需要考虑所有可能的情况，这里考虑最后一种的消除方法，可以是最后剩下的1/2/3个相同元素消除。

一种经典的转移方法是枚举分成两半，即枚举中间点k，f[l][r]=max(f[l][k],f[k+1][r]),可以理解为分开消除区间[l,k]和[k+1,r]。这种经典的转移可以囊括不包含端点对在内的1/2/3元素消除。

端点l和端点r之间的相等的情况会是上述转移无法考虑到的，即最后留下l和r两块相同的砖消去，需要考虑f[l][r]=max(f[l][r],f[l+1][r-1]+max(a*2,b))，二者相同可以消一次*2也可以直接用消两次的代价。