D. Almost Triple Deletions（dp/逆向思维/好题）

题目

参考

题意

给定长度为n的数组，现在可以执行若干次操作 如果a[i],a[i+1]不相等，则从数组a中消去元素a[i],a[i+1]，将剩余元素按原来顺序，拼接成新数组a。 问最终能得到的、元素都相同的数组，长度最大是多少。

思路

没有脑洞是想不到，正向思路想半天想不来，去偷瞄了下官方题解。

逆向思考，什么情况下，可以将数组都消去，使得剩余元素个数为0呢？需要满足2个条件。

• 首先，数组长度要是偶数，如果是偶数，至少会剩下一个元素消不去。
• 其次，数组中，出现次数最多的元素（不妨称它为x）个数，要不超过n/2，这样的话，我们每次选择与x相邻的、且值 不相等的元素去做消除，最终一定可以将所有元素消去。

定义dp[i]，表示以第i个元素结束，能得到的取值都为a[i]的数组的最大长度。

以下所有说明，是以数组下标，从0到n-1，为基础。

1、初始化

dp[0]=1。 对于大于0的下标i，如果数组a[0],…a[i-1]能完全消去（长度为0，且max_count