【魔怔】拼接。记忆。破碎。

· · 题解

你是一名因水平原因而遗憾退役的 OIer。退役之际，你正努力寻找和拼接着你在 OI 生涯中的回忆。

按顺序，你有 n 片关于 OI 的记忆，每一片用一个数字 a_i(1\le a_i\le 20) 代表，数字相同代表记忆内容相近。

你想把其中最具有代表性的记忆拼接在一起，可以不在原序列中连续。具体地，你要求出一个 a 的可不连续的子序列，其中两片相近的记忆（a_i=a_j）需要在子序列中连续。同时，你不想让过多重复的记忆进入，所以每一片记忆的内容只会出现 0 次或 2 次。

请求出你所获得的回忆子序列的最长长度。

你马上想到，可以使用状压求出分别是否选择了 20 种内容。记 S 为当前状态的二进制值，从低到高第 i 位为 1 代表已经被选择，为 0 代表未被选择。

你考虑从小到大枚举 S，并记录能达到这种状态的最小的下标 f_i（如果无法达到，f_i=\infty）。你很显然地发现，对于一个状态 S，通过枚举往后延展回忆的内容编号（1\sim 20）来进行转移即可高效地完成。

具体地，设当前状态为 S（f_S\ne \infty），被延展的回忆内容编号为 x（S 开始时从低到高第 i 位不能为 1），则新状态的编号为 S'=S+2^{x-1}。S 能够向 S' 转移的充要条件，即是在 f_S 之后，仍然有两个下标 j,k 满足 a_j=a_k=a_{f_i}，且 k<f_{S'}，则此时即可让 f_{S'}=k。

你也发现暴力地求出 j,k 是低效的，于是你预处理了一个 nxt_{i,j}，代表从下标 i 开始下一个值为 j 的下标，于是解决了这道题。

你的代码。

你成功地把你 OI 生涯中最具代表性的事物留在了脑海中，可你却仍感空虚。仅用至多 40 片回忆来代表这近乎数万的记忆，未免有所片面。因为，你的 OI 生涯里有太多美好。

回望这些回忆，你忽而感到它们在破碎。正因缺少了什么，或是前因后果，或是平凡琐事，你感觉它们都失去了意义。越往深入去想，你的自我怀疑越深，情绪也越崩溃。可于千钧一发之际，你似乎找到了一切的答案，它能够串联起你的整个 OI 生涯，不遗留，也无遗憾。

这就是你热爱 OI 的心。